PDA

View Full Version : Plotting routes on a grid



Gadget
28-02-2003, 12:38 PM
Can anyone suggest a quick way of working out a route from one point to another on a simple grid of say 64 tiles?

Ultra
01-03-2003, 01:18 AM
Wasn't there a tutorial about these sort of things in the tutorial section (A*). Or is it just that I have totally misunderstood the question?

cairnswm
03-03-2003, 04:51 AM
There is a tutorial on the A* algorithm in the tutorials section. For the tutorial I've used a stringgrid to display the information so that it it is possible to see how the route is calculated.

Displaying the route on the grid is not included in the tutorial but an explanation on how to find the route is.

Gadget
10-04-2003, 11:30 AM
For what I need, I ended up coding a very simple routine...

Basically, for each step move one square nearer in the X position if possible, and move one square nearer in the Y position if possible. Store positions previously moved, and if you hit a dead end, work you way backwards trying alternative routes not in your 'walked' list.

I can post the code afterwards, it's not as good as A* but it works for what I need.

cairnswm
11-04-2003, 05:21 AM
That is basically the logic behind A* anyway.

The key is keeping a priority list of unwalked paths. I did this in a String List. The problem with the logic you are using is that it may take tooo long to find the path if it isn;t in a reasonably direct route. The reason I called my algorithm Nearly A* is because it has the same problem - I try to walk striaght to the desitnation instead of in all possible directions at the same time.