Jump to content
  • Advertisement
Sign in to follow this  
  • entries
  • comments
  • views

A Star Update

Sign in to follow this  


A Star Update

Well, I've been working on AStar this week. Last time I talked about switching to a dense waypoint mesh. This seems like a good choice so far.
I've been using some free AStar code from the net, which keeps crashing on me at certain points, so I've been reading numerous good tutorials on the subject in order to get ready to write my own.

It's amazing how, with so much code available on the net, very little can be directly used in a project. There are just too many assumptions and tradeoffs that must be made to make something usable for a certain purpose. And building these tradeoffs into the interface often serves to obfuscate the simpler uses of the code.

For my project, the map size will be up to about 128x128 in size, or 32k nodes. This can have implications regarding how you store the open & closed lists.

For the open list, you are inserting ~8 nodes for every node that you visit, so insertions should be relatively quick. But, you also need to find the cheapest node at each step in the algorithm, so having something sorted seems like the right approach.

For the closed list, the group of things you've already visited, you just need a quick way of checking if you've come to a node already. There are also cases where you may want to remove something from the closesd list ( rare ), but you need to check every node to see if it's on the list already ( often ).

The code I was using used the std::heap functions on a std::vector for the open list, and a linked list for the closed list, and seemed pretty fast.

A Few Hours Later :

I have since written & tested my own implementation. After trying to digest the std::heap functions, I'm not sure what advantage they have over storing the open list as a std::vector, and calling sort before you need the cheapest element ( stored at the end of the array ).

Tomorrow I may try the heap functions again to see if they are faster, but I'm not super-worried about it right now.

You can make some more optimzations if you have small map like I do, like storing the closed list as a grid or an array, for fast lookup, insertion and removal. Of course, if you have more than one path search in effect at any one time, you need a separate grid for each search.

My code is structured around the idea of an object called AStar_Search. You can call it with a maximum # of nodes to try, and it will quit early, while saving its progress, to be restarted later. For my purposes, A star will be used mainly for relatively short paths. The AI will use it to travel from room to room when on patrol, and to follow the player. Of course, the enemies won't have perfect sight of the player at all times, so if the player goes offscreen or behind something, they will path to the last place they saw the character, which by definition must be closeby.

So, I won't spend too much time optimizing this any further, as it seems to run well, and most importantly, doesn't crash like the old a star code! ;)

One of the cool tricks I added to my a star cost function was a penalty to any nodes that were at an edge of the walkable area. This is done by simply penalizing walking into any node that doesn't have all 8 valid neighbors. This tends to keep the enemies from hugging walls and bumping into corners. I temporarily took out true walk-checking from version of the navigation system, which I will add tomorrow now that I have the new capsule collision code.

Here is a shot of the path found and the closed list ( all of the nodes checked ).

Here is a shot of my temple level, with a round pool of water, which was made with the new hemisphere morph tool.

Sign in to follow this  


Recommended Comments

Hey Sim dude, was getting concerned as your journal wasn't updated in a couple of days :D
Anyway, is there a way you can smooth out that pond edge that is casting shadows on the water?

Share this comment

Link to comment
The edge of that pond does need a bit of work [smile]

wrt A* though... have you stress-tested it with multiple agents yet? that's the one that caught me out in a little RTS I made a few years back - 2 or 3 (+ player) was no sweat on my machine... but when I had 30-40 enemy units the whole thing kinda broke down to a slideshow. Wasn't hard to fix it, but it ceased being a trivial algo [headshake]

Keep up the good work!


Share this comment

Link to comment
Yes, the pool edge is already fixed. This is an example where the lighting in the editor didn't clearly show the faceting, so I had to get back & fix it after seeing it in-game.

In retrospect, I should have tessellated the pool more. I can do that easily enough, and then I can go in a apply a 'smooth vertices' operation - this moves all selected verts towards the average pos of their neighbors along the vertex normal.

Luckily, I won't have to deal with 30-40 units, only ~8 at the very most. Maybe 6 or 7 enemies and 1 or 2 ambient creatures.

The main thing I will do as an optimization is simply to break the path finding up into multiple tries. I just made this change to the code and am about to test it.

Share this comment

Link to comment

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!