Taste of Success - The first semester edition

Hello everyone!

Recently, I have encountered some success in the development of our game! Currently we have an AI system that works off of a A* algorithm (More detail in later), and from the A* algorithm I use Catmull-Rom to move the player object towards the destination, using a Distance/Speed calculation, to find my Segment time, then interpolating along that.


Moving towards the more specific, just in case anyone reading out there actually wants to know what I was talking about! A* is an algorithm that takes the game world, and arranges it into a large grid. The boxes or sectors of this grid have either a Yes or No value. Yes being that the sector is free, and there are not obstacles in the way, and obviously No when the sector is occupied. Now one might ask "Why would this be useful at all?" Well that would be a great question! It allows an AI character to move along a certain path, for example towards a goal without hitting obstacles or moving off course.

Here is an example: Say our destination block is at Sector 4 which is right from our starting point Sector 1.

Sector 1

Sector 2

Sector 3

Sector 4

There is a cute little graphical representation, Again Sector 1 is our START point and Sector 4 is our END point or goal destination.

For an AI character to move from Sector 1, towards Sector 4, it checks all of the sectors around its current sector, then it evaluates the shortest path to Sector 4, without going through obstacles. Now this example, would just simple end if I put an obstacle say at Sector 3.

However simply speaking that is how a A* algorithm works, finding the shortest path towards the goal destination, without needing to go through obstacles. Here is finally that document online I was telling you all about -> Reading on A* Algorithm from Wikipedia.

Also in reading that document I also found a very nice graphical representation that I feel explains exactly the process I was speaking on above with my cute little chart, be forewarned though this graphical image blows my little chart out of the water! From: Wikipedia Article on A* 

The only difference between this image and the explanation that I was going for is that the actual algorithm in this case is weighting each of the dots (sectors) by shortest path (represented by colors Red to Green).

So there is that on A*! Since we already spoke about Catmull-Rom in another post I do not feel that my readers will want me to go over that all over again! However if anyone needs help with Catmull-Rom and is reading this, or has read my previous post and needs some advice please do not fear commenting, I will do my best to answer your question and provide useful articles that have helped me in the past. IF by some WEIRD chance you did not get to see my previous post! Just click "Journey to Second Semester" on the side right above my profile!

Thanks a bunch for reading! Look forward to more!

See you all soon!

Regards,

Stephen Krieg

Source Image link

Journey Towards Semester Two

Our journey in second semester of Game Development begins with finding out that three of our five group members have elected to leave the course and not continue forward with the Game Development program. As most would assume this is a very bad situation for those of us left in the program, as there are currently only two of us left. Head over to braydenmyers.blogspot.ca to check out his posts. I figured as we are the only ones left in our group you out there should have a full view of the progress on our game as seen through the eyes of the only two surviving members of the first semester!

Moving forward from the depressing reality of our current group situation, our game "Journey To Posidonia". I wouldn't say we are behind, I much prefer the term "set back", due to the fact that only two of our five group members ever did any work on our game. Having problems with Catmull-Rom interpolation, for some reason I am getting high values in the millions, when the current size of our map is literally 0 - 10000, I feel like there are brackets missing in certain spots in our calculation, however I have yet to figure out exactly what the problem is. I have used external resources, I have even copy/pasted code from stackoverflow.com into our code for the sake of testing purposes (note, I never copy the code and keep it in there, simply for testing purposes). Any-who that still doesn't work to get the problem solved, so I have resorted to completely re-work my calculations in my path.cpp to attempt to find the problem, which I believe again to be a surplus or lack thereof of Brackets in the formula.

If anyone is interested here is a link to the stackoverflow post I was using. --> StackOverflow

Oh and if you are really interested here is the link to Wikipedia where you can see the actual formula and read up on how it works, but I am going to explain it in just a few seconds here so if you feel like listening to me more then that is great! 

So basically splines are curves, mostly they are used for path finding, and AI path following. However they have multiple uses, for example, the Bezier spline is most commonly found in Photoshop in the "pen tool" (great tutorial if anyone is interested.) Catmull-Rom however relies on Four points: The two Points you are interpolating between (Usually called interpolation points), and the points preceding and following your interpolation points.

At great graphical representation of Catmull-Rom is included below: Source Link

So given those four points, you interpolate along a specific segment (between P1 and P2) over an interpolation value  most commonly denoted as: t (0 , 1). 

In our game we are planning to use this technique to move our AI characters from point to point towards the player, this will allow them to move smoothly and not in a rigid line formation (kind of how everyone tells you Alligators run if you can imagine that and keep a straight face that is). We feel like this is the best way to do this, now there is the possibility of using acceleration, however that would leave our AI characters sliding at times, which is not the desirable result we are looking for. 

So that is a basic explanation of Catmull-Rom, again if you would like more information, I do urge you to check our the wiki article that I posted above, it is very technical but includes most if not all the information that you should need to know before attempting Catmull-Rom, or even if you want to simply check out how it works!

I will keep everyone updated on our progress, and if anyone is interested in seeing the code I am using to attempt to make Catmull-Rom interpolation work, I would be more than happy to post it for those of you who would like to see it! However for now I will simply leave it at that, post a comment if you would like to take a gander.

With that I leave you with a last small piece of advice, to all those aspiring game developers out there!

- If you want something work for it, because there is no one or nothing that can stop you from getting what you want, if you truly want it.

Thanks for reading!

Regards,

Stephen.

Source Link