Applying A*

[Einheri]

Hi, I've been working on a graphic adventure game in Java for a short while now, and I've just about botched together a working A* Algorithm that I intend to use for the point and click walking in the game. However, I'm still a bit unsure as to how to implement it. I've never seen any information on how these games are made, so I have no idea how the 'pros' do it, which means I've had to come up with a few guesses.... none of which seem like the best way to do it.

My main idea at the moment is to have a pre-defined network of nodes for each scene (perhaps detailed in an XML file, methinks) and then to dynamically create nodes at both the position where the player sprite is, and where the user has clicked. The only problem with this is, I'm unsure as to how I would determine the neighbour nodes of the two dynamic ones. I've thought about a system of finding the nearest nodes, but this is unsatisfactory, as those nodes could be behind an obstruction, or something.

Another Idea I had was to dynamically create a whole uniform grid of nodes every time the user clicks to walk anchored around the start and end positions, and putting nodes on the closed list based on an image with the no-go areas blacked off. This seems amazingly inefficient, though.

Right, so none of these seems quite right, so I'm hoping that someone here has a better head for these things than I do! does anyone have any suggestions as to how I'd go about doing this?

Thanks a lot.

[Ed Mack]

Game programming Gems 1 has some good articles on this, if you can look through a copy do it :)

You should tell us more about the type of space we are searching.

You could define the world as a network of connected areas covering all of the game world, and then whichever area the player is in is the first search node. This will only work for a world that is broken up a lot.

[Einheri]

Well, I'm basically just searching a flat 2D area (the screen co-ords of the player to those of the mouse click). The method you've suggested would work well for a multi-room game, but each scene in this will be pre-rendered and, therefore, pretty open (which is why it's such a problem).

I'll look into GPG1 (I might be able to sneakily flick through it at a local book shop, or something), though, thanks a lot for the suggestion.

[m4x0r]

One typical solution is instead of thinking of your A* graph as infinitely small nodes connected by lines, just think of it as a triangular mesh. Each triangle is a node, and triangles which are connected by an edge are connected in the graph.

This way you can easily build a mesh representing the walkable surface in 3D Studio MAX or some other content creation package.

Using a triangular mesh you can also create paths which look more natural, since they can pass through any point along the connecting edge of the triangles, instead of one pre-defined line.

If you do manage to check out GPG1 you'll see some good examples of this.

Max

[NomadRock]

As far as I am concerned there is only one source to learn it from Amit does an amazing job of explaining not only how it works, but why it was developed the way it was.

http://theory.stanford.edu/~amitp/GameProgramming/

[Einheri]

One typical solution is instead of thinking of your A* graph as infinitely small nodes connected by lines, just think of it as a triangular mesh. Each triangle is a node, and triangles which are connected by an edge are connected in the graph.
20432


That is quite a good idea, actually, brilliant in its simplicity. I'd considered a square grid but thought that it would make movement far too quirky; I just didn't think to use tiangles! Thanks a lot for the suggestion... now to make it work:- I guess that's bye bye bank holiday (and beyond...)!

And Nomad, that site was a great help while writing the algorithm, but now I've got it I need to make it work!