Game Development Stack Exchange is a question and answer site for professional and independent game developers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am making car racing game. I stuck with the AI of the game. I go through with the A* search, but there is problem that I want to ask that whether we have to make a 2D array and than apply search on that array. 2D array mean a grid, to which we apply the search algorithm.

Can an A* path-finding implementation be practically implemented on data-structures other than a square 2D array?

share|improve this question

closed as not a real question by msell, Anko, Josh Petrie, BlueRaja - Danny Pflughoeft, Maik Semder May 24 '13 at 19:07

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

That question as edited in by Pieter is interesting, but still too vague to be answerable: What other data structure is it that A* should be implemented on? Why would anyone want or need to do this? – Anko May 26 '13 at 23:32
@Anko, the standard data structure that A* is applied to is a general graph, not a 2D grid, and a general graph would be useful anytime you want to do pathfinding in a world that doesn't happen to be shaped like a 2D grid. IMO this is a specific-enough question at this point and Pieter has answered it correctly. – Nathan Reed May 27 '13 at 20:25
up vote 2 down vote accepted

The A* algorithm requires hat the set of possible agent locations be discrete, not continuous, and that there be a connectivity relation between the set of possible locations, called nodes.

A well-written A* algorithm will not require any particular storage choice for the nodes and the connectivity, but will use Inversion of Control to obtain the adjacent nodes for each node under consideration from the client.

Eric Lippert has written a very good A* exposition here. that can assist you in seeing how this is done.

share|improve this answer
Minor issue - A* doesn't have a hyphen in it – Polar May 25 '13 at 14:55
You say "to-mah-to" and I say "to-may-to". I have seen it both ways – Pieter Geerkens May 26 '13 at 18:30
@PieterGeerkens No, Polar is correct - A* written A*, not A-*, in Wikipedia, books, blog posts (including the ones you linked to), etc. The only place it's written with a hyphen is when writing it out in words, like "A-star". I've rolled back to Polar's edit correcting it. – Nathan Reed May 26 '13 at 21:01

Not the answer you're looking for? Browse other questions tagged or ask your own question.