Jump to content

  • Log In with Google      Sign In   
  • Create Account

We're offering banner ads on our site from just $5!

1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.


A* Implementation Question


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
6 replies to this topic

#1 Silgen   Members   -  Reputation: 178

Like
0Likes
Like

Posted 24 November 2012 - 12:36 PM

I have been reading about the A* algorithm recently, and I want to implement it myself to make sure that I fully understand it. What is the best way of representing the map that will be searched? Array? A tree of some kind?

Sponsor:

#2 SiCrane   Moderators   -  Reputation: 9630

Like
0Likes
Like

Posted 24 November 2012 - 12:44 PM

There is no best way. Representation of the search space is orthogonal to functioning of the A* algorithm.

#3 Silgen   Members   -  Reputation: 178

Like
0Likes
Like

Posted 24 November 2012 - 12:51 PM

Okay - then perhaps my question should have been - which representation of the search space will make running the A* algorithm on it easiest? What method is most commonly used?

#4 Álvaro   Crossbones+   -  Reputation: 13693

Like
1Likes
Like

Posted 24 November 2012 - 12:56 PM

There is no best way. Representation of the search space is orthogonal to functioning of the A* algorithm.


I am not sure that is entirely true. Whatever algorithm you are going to use determines what types of accesses to the data you are going to be doing most frequently, and thus what representation might work best.

In the case of A*, however, all you need from the graph is iterating through the nodes that are connected to a given node, which is the most basic thing you can ask from a graph. If your map is a grid (like in an RTS), the obvious array is a perfectly good representation. If not, a sparse graphs (with lists of connections for each node) is probably what I would use.

#5 ultramailman   Prime Members   -  Reputation: 1582

Like
0Likes
Like

Posted 24 November 2012 - 01:02 PM

Hello
If you have a square map with tiles, you can use a 2d array. Each element will of the array can contain some information about the space it represents. Let's say you have a room of bricks, and the bricks are perfectly aligned to each other; element [3][4] will represent the brick whose upper left corner is at position
(x = 4*BRICK_WIDTH, y = 3*BRICK_HEIGHT).

#6 SiCrane   Moderators   -  Reputation: 9630

Like
2Likes
Like

Posted 24 November 2012 - 02:23 PM

Okay - then perhaps my question should have been - which representation of the search space will make running the A* algorithm on it easiest? What method is most commonly used?

You're looking at it from the wrong direction. Come up with a situation where you would want to use pathfinding. Create a representation suitable for that situation, and then figure out how to use A* with that representation.

In the case of A*, however, all you need from the graph is iterating through the nodes that are connected to a given node, which is the most basic thing you can ask from a graph.

Which is why I think that representation is orthogonal to A*. If you've got a representation where you can't efficiently determine node transitions, then you're representation will also be inefficient for pretty much any operation, not just search algorithms. Obviously, if you're going to choose a representation for the search space which is inefficient for general use, then of course it's going to be sub optimal for A*. The point is to come up with a representation that makes sense for the system being modeled.

#7 Postie   Members   -  Reputation: 1087

Like
0Likes
Like

Posted 25 November 2012 - 04:28 AM

A very common use for A* Pathfinding is discovering the optimal path across a series of 2d tiles or a uniform grid. This is typically represented using an array.
Currently working on an open world survival RPG - For info check out my Development blog: ByteWrangler




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