-1
\$\begingroup\$

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?

Improve this question
\$\endgroup\$
2
  • \$\begingroup\$ 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? \$\endgroup\$
    – Anko
    May 26 '13 at 23:32
  • \$\begingroup\$ @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. \$\endgroup\$
    – Nathan Reed
    May 27 '13 at 20:25
2
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ Minor issue - A* doesn't have a hyphen in it \$\endgroup\$
    – Polar
    May 25 '13 at 14:55
  • 1
    \$\begingroup\$ You say "to-mah-to" and I say "to-may-to". I have seen it both ways \$\endgroup\$
    – Pieter Geerkens
    May 26 '13 at 18:30
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – Nathan Reed
    May 26 '13 at 21:01

Not the answer you're looking for? Browse other questions tagged .