Jump to content
  • Advertisement
Sign in to follow this  
KnolanCross

Improving my A* implementation

This topic is 2056 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello there, I implemented my own A* a few months ago, it is grid based an uses an unordered list to keep the open list, in other words, it is pretty much the worst implementation performance-wise. It is fast enough for my needs, but I want to improve it, I implemented a heap for it and I also wanted to use a region approach.

 

So far my algorithm converts reagions, those regions turn into a graph, and the A* will operate on this graph. For instance, this input (where 0 means that the tile is not walkable and . means that it is):

 

000000000
0.......0
0..0....0
0.......0
0.....0.0
0000000.0

Will be converted to this region map:

00 00 00 00 00 00 00 00 00 
00 01 01 02 03 03 03 04 00 
00 01 01 00 03 03 03 05 00 
00 06 06 07 03 03 03 08 00 
00 06 06 09 10 11 00 12 00 
00 00 00 00 00 00 00 13 00 

This is a visual representation of the graph, all the same numbers (but the 00) are a region (every region is a square of size N) that are converted to a node in the graph. Each neighbor region has an edge with the cost so I can run the A* on the graph. The problem is, once I got the A* path, how do I navigate to it?

 

For instance, If I want to go from region 03 to region 02, I can go directly, but if I am at the botton left part of region 03 and try to go to region 02, I would cross a wall trying to go in a straight line.

 

Any ideas on how to use this approach? I was trying to do something similar to a navmesh (my game is 2d), to reduce the node number, but I am pretty stuck now.

 

 

Edited by KnolanCross

Share this post


Link to post
Share on other sites
Advertisement

I would avoid using regions if you can get the more naive solution to run fast enough. How big is your map?

Share this post


Link to post
Share on other sites
This is a simplified form of navmesh pathing; you can probably draw some inspiration from the way navmesh pathfinding + steering are typically implemented.

However, as Alvaro suggested, it may be worth just doing the simple thing. You can easily path through hundreds of thousands of nodes in realtime if necessary with a good A* implementation.

Share this post


Link to post
Share on other sites

Yes, I thought that this should be similar to a navmesh navigation, but I couldn't find any good material on that, the best I could find was this one:

http://blenderartists.org/forum/showthread.php?231535-How-Navigation-Meshes-%28NavMesh%29-work-compared-to-WayPoint-graphs

 

Most of the other say you can simply walk from one point to another, which is not truth in my case. If anyone got a good link, I am curious to read some more about it.

Edited by KnolanCross

Share this post


Link to post
Share on other sites
If your region allocation is done correctly, it should just be a matter of projecting a ray from the current position to the nearest edge of the next region on the path, and steering along that ray. There are of course a host of issues around path smoothing and realistic turning you can consider later, but that should get you started.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • 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!