An admissable heuristic for traversing a grid.
by Hans Sjunnesson · in Torque Game Builder · 09/13/2005 (2:51 am) · 6 replies
I'm implementing a tree-searching algorithm, and I'm having some trouble coming up with an admissable heuristic for my A* algorithm.
Basically, I have a rectilinear grid of tiles. Some tiles have active collisions on them, filling the entire tile, making a neat little maze. The agent who is pathfinding in this maze can traverse only to bordering tiles which have inactive collisions, meaning he can't move diagonally.
At first, I used the vector distance between the considered tile and the end tile which, granted, is an admissable heuristic, it never overestimates the cost of getting there, but since the world is discreetely partitioned, it's not really a good metric.
I then look at line drawing algorithms, which are great. The idea of a line-drawing algorithm is to step through a grid of pixels and light up pixel for pixel. The Bresenham line-drawing algorithm gave me an integer number of how many pixels it would light up from "here" to "there", which is exactly what I want.
BUT... no line-drawing algorithm I know of draws fully connected "lines" of pixels.
To demonstrate, say I wanted to draw a line from square "0 0" to "9 9" in this 10x10 grid of squares, the Bresenham algorithm would produce this:
But what I need, is something like this:
Or this:
It's the same thing when you use a different slope too, Bresenham draws this:
What I need, of course, is someting like this:
You see where I'm getting at? Anyone know an algorithm that has these properties, or know of a better way of solving things?
--
Hans
Basically, I have a rectilinear grid of tiles. Some tiles have active collisions on them, filling the entire tile, making a neat little maze. The agent who is pathfinding in this maze can traverse only to bordering tiles which have inactive collisions, meaning he can't move diagonally.
At first, I used the vector distance between the considered tile and the end tile which, granted, is an admissable heuristic, it never overestimates the cost of getting there, but since the world is discreetely partitioned, it's not really a good metric.
I then look at line drawing algorithms, which are great. The idea of a line-drawing algorithm is to step through a grid of pixels and light up pixel for pixel. The Bresenham line-drawing algorithm gave me an integer number of how many pixels it would light up from "here" to "there", which is exactly what I want.
BUT... no line-drawing algorithm I know of draws fully connected "lines" of pixels.
To demonstrate, say I wanted to draw a line from square "0 0" to "9 9" in this 10x10 grid of squares, the Bresenham algorithm would produce this:
But what I need, is something like this:
Or this:
It's the same thing when you use a different slope too, Bresenham draws this:
What I need, of course, is someting like this:
You see where I'm getting at? Anyone know an algorithm that has these properties, or know of a better way of solving things?
--
Hans
#2
Oh sure, I did switch to eight degrees of freedom, and then any given line-drawing algorithm gives you exact cost results (even though engine-side distance measurement is probably faster). However, for this given example, diagonal movement wasn't allowed, so I wanted an algorithm that didn't skip pixels and "move diagonally" either.
--
Hans
09/13/2005 (9:28 am)
@GaryOh sure, I did switch to eight degrees of freedom, and then any given line-drawing algorithm gives you exact cost results (even though engine-side distance measurement is probably faster). However, for this given example, diagonal movement wasn't allowed, so I wanted an algorithm that didn't skip pixels and "move diagonally" either.
--
Hans
#3
10/15/2005 (9:24 pm)
This is probably too late, but what you want is often called "Manhattan Distance". It is very simple (no need to compare it to Bresenham). Add up the horizontal plus the vertical distances. H = abs(x1 - x2) + abs(y1 - y2). If you count it up, it is actually the same thing that you were drawing in your diagram.
#4
In my game I needed to shuffle some tiles and instead of writing complex equations describing shuffling behavior, I just setup collision properties, and gave the tiles a strong WHACK. (applied a force). Very cool effect, with relatively little coding :-)
10/15/2005 (9:54 pm)
Why use a path finding algorithm when you have T2D physics? Just mount the agent to a hidden object on the other side of the maze, turn on all your collision properties let 'er rip. Seriously it's worth playing around with!In my game I needed to shuffle some tiles and instead of writing complex equations describing shuffling behavior, I just setup collision properties, and gave the tiles a strong WHACK. (applied a force). Very cool effect, with relatively little coding :-)
#5
10/15/2005 (9:57 pm)
Oops- old thread, and I realized you all are talking strictly about optimal solutions to path finding problems. Never mind!
#6
--
Hans
10/16/2005 (12:42 am)
Thanks James, for your addition. It's never too late to add something to an old thread. It's helpful if someone is searching the forums with the same kind of problem.--
Hans
Torque Owner Gary Preston
Theres quite a few good tutorials on the variations of A*, one I read a while back and based my first implementation off was www.gamedev.net/reference/articles/article2003.asp