• FEATURED

View more

View more

View more

### Image of the Day Submit

IOTD | Top Screenshots

### The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

# 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.

5 replies to this topic

### #1KnolanCross  Members

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).

### #2Álvaro  Members

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?

### #3KnolanCross  Members

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).

### #4ApochPiQ  Moderators

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.
Wielder of the Sacred Wands

### #5KnolanCross  Members

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:

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).

### #6ApochPiQ  Moderators

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.
Wielder of the Sacred Wands

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.