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
No comments:
Post a Comment