Jump to content

  • Log In with Google      Sign In   
  • Create Account


Improving my A* implementation


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
5 replies to this topic

#1 KnolanCross   Members   -  Reputation: 1271

Like
0Likes
Like

Posted 29 April 2013 - 11:18 AM

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, 29 April 2013 - 11:19 AM.

Currently working on a scene editor for ORX (http://orx-project.org), using kivy (http://kivy.org).


Sponsor:

#2 Álvaro   Crossbones+   -  Reputation: 12917

Like
0Likes
Like

Posted 29 April 2013 - 11:27 AM

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



#3 KnolanCross   Members   -  Reputation: 1271

Like
0Likes
Like

Posted 29 April 2013 - 11:41 AM

Right now they are very small, I limited to 100x100 and haven't reached the limit yet.


Currently working on a scene editor for ORX (http://orx-project.org), using kivy (http://kivy.org).


#4 ApochPiQ   Moderators   -  Reputation: 15062

Like
0Likes
Like

Posted 29 April 2013 - 12:11 PM

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.

#5 KnolanCross   Members   -  Reputation: 1271

Like
0Likes
Like

Posted 29 April 2013 - 12:45 PM

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, 29 April 2013 - 12:46 PM.

Currently working on a scene editor for ORX (http://orx-project.org), using kivy (http://kivy.org).


#6 ApochPiQ   Moderators   -  Reputation: 15062

Like
0Likes
Like

Posted 29 April 2013 - 12:51 PM

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.




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS