Finding the Best Path

On Jan 28, 4:45 pm, tyreciu... DeleteThis @yahoo.com wrote:
> There are two potential solutions. The simpler one by far is to weight
> diagonal movement slightly higher (or even \sqrt(2)) than orthogonal
> movement. The more complex one is to break ties in favor of orthogonal
> movement.

Thanks. I made the change within about a minute; I have no idea why I
didn't think of this before.

--
Gamer_2k4
 >> Stay informed about: Finding the Best Path 

On 28 ene, 19:31, Gamer_2k4 <gamer... RemoveThis @gmail.com> wrote:
> On Jan 28, 4:45 pm, tyreciu... RemoveThis @yahoo.com wrote:
>
> > There are two potential solutions. The simpler one by far is to weight
> > diagonal movement slightly higher (or even \sqrt(2)) than orthogonal
> > movement. The more complex one is to break ties in favor of orthogonal
> > movement.
>
> Thanks. I made the change within about a minute; I have no idea why I
> didn't think of this before.
>
> --
> Gamer_2k4

That is why is a good idea to study a little what the Masters said in
the past about path finding. The Dijkstra algorithm use a similar
method for finding the shortest path between two points.
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

-
/\+++/\
< agnas >
\/+++\/
 >> Stay informed about: Finding the Best Path 

On Jan 29, 7:52 am, Christophe <chris.cavala... RemoveThis @free.fr> wrote:
> Gamer_2k4 a écrit :
>
> > On Jan 28, 4:45 pm, tyreciu... RemoveThis @yahoo.com wrote:
> >> There are two potential solutions. The simpler one by far is to weight
> >> diagonal movement slightly higher (or even \sqrt(2)) than orthogonal
> >> movement. The more complex one is to break ties in favor of orthogonal
> >> movement.
>
> > Thanks. I made the change within about a minute; I have no idea why I
> > didn't think of this before.
>
> I had faced the same issue as you before when implementing a djikstra,
> but it was much more puzzling for me because I had been working up to
> now on another project that used A* as a path finder and they didn't
> have such issue. I found that the heuristic choice in A* will have quite
> a lot of effect on the solution chosen when you have multiple solutions
> with the same cost.
>
> So, the idea is to have a grid with an infinite norm movement costs as
> you have currently (all directions cost 1) but implement A* with a sqrt
> type norm as the heuristic used. You should get nice paths that look
> like bresenham lines in the open rooms with that.

I actually didn't use either Djikstra or A*. I used a recursive
distance mapping algorithm based on this article:
http://roguebasin.roguelikedevelopment.org/index.php?title=Quick_Pathf...ing_in_

Then I used a walker method to travel back along the numbers,
generating a list of points as I went. It checked the points around
it like this:

for (int i = -1; i <= 1; i++)
{
for (int j = -1; j <= 1; j++)
{
if (distMap[x + i][y + j] < smallest || (distMap[x + i][y
+ j] == smallest && Abs(i) != Abs(j)))
{
sX = x + i; sY = y + j; smallest = distMap[x + i][y +
j];
}
}
}

Basically, if the current tile has a smaller distance than a previous
one, make that the next tile. If it has the same distance, but isn't
on a diagonal (Abs(i) != Abs(j), true only when one of them is zero),
then pick that one instead.

It may seem foolish to map the whole dungeon for distance, and it is.
I limit the mapped area to what the monster can see. There is a
noticeable slowdown (not significant though), but I also have certain
optimizations that keep the mapper from being called unnecessarily.

--
Gamer_2k4
 >> Stay informed about: Finding the Best Path 

On Jan 29, 8:19 am, David Damerell <damer....DeleteThis@chiark.greenend.org.uk>
wrote:
> Can you track the number of direction changes in a path and arrange to
> prefer paths with fewer, if they are of equal length?

I tried a method based on continuity, where, if given multiple options
with the same move cost, the walker would pick the tile that allowed
it to continue in the same direction, and it wasn't anything special.
The other option (I think) would be to recursively travel on every
possible path, and it seems like a lot of extra processing time just
to get a path of the same length that only looks nicer.

--
Gamer_2k4
 >> Stay informed about: Finding the Best Path 

On 29 ene, 10:20, David Damerell <damer....DeleteThis@chiark.greenend.org.uk>
wrote:
> Quoting agnas <gustav....DeleteThis@gmail.com>:
>
> >That is why is a good idea to study a little what the Masters said in
> >the past about path finding. The Dijkstra algorithm use a similar
> >method for finding the shortest path between two points.
>
> That's not the issue here; in roguespace, Gamer2k's awkward paths _are_
> equal-shortest to the preferred ones.
> --
> David Damerell <damer....DeleteThis@chiark.greenend.org.uk> Kill the tomato!
> Today is Stilday, January - a weekend.

Are you saying that using the Dijkstra algorithm the resulting path
will be the number 1option below???+

Option 1: a longest path.

#################
##.....89ABCDE.##
##....7.......F##
##...6.........GH
##..5..........##
##.4...........##
##3............##
12.............##
#################

Option 2: THE shortest path

#################
##.............##
##.............##
##...6789ABCDEFGH
##..5..........##
##.4...........##
##3............##
12.............##
#################

I only said this:
1) Its a good idea study algoriths freely available in the internet.
2) The Dijkstra algorithm is a good solution for this kind of path
finding problems.

Cheers,
-
/\+++/\
< agnas >
\/+++\/
 >> Stay informed about: Finding the Best Path 

Quoting Gamer_2k4 <gamer2k4.RemoveThis@gmail.com>:
>Let's say that my dungeons have no concept of rooms versus halls (in
>other words, entrances and exits of rooms aren't tracked). What's the
>best way to smooth the path?

Can you track the number of direction changes in a path and arrange to
prefer paths with fewer, if they are of equal length?
--
David Damerell <damerell.RemoveThis@chiark.greenend.org.uk> Kill the tomato!
Today is Stilday, January - a weekend.
 >> Stay informed about: Finding the Best Path 

Quoting agnas <gustavorg RemoveThis @gmail.com>:
>That is why is a good idea to study a little what the Masters said in
>the past about path finding. The Dijkstra algorithm use a similar
>method for finding the shortest path between two points.

That's not the issue here; in roguespace, Gamer2k's awkward paths _are_
equal-shortest to the preferred ones.
--
David Damerell <damerell RemoveThis @chiark.greenend.org.uk> Kill the tomato!
Today is Stilday, January - a weekend.
 >> Stay informed about: Finding the Best Path 

On 29 ene, 13:36, David Damerell <damer....DeleteThis@chiark.greenend.org.uk>
wrote:
> Quoting agnas <gustav....DeleteThis@gmail.com>:
>
> >On 29 ene, 10:20, David Damerell <damer....DeleteThis@chiark.greenend.org.uk>
> >>That's not the issue here; in roguespace, Gamer2k's awkward paths _are_
> >>equal-shortest to the preferred ones.
> >Are you saying that using the Dijkstra algorithm the resulting path
> >will be the number 1option below???+
> >Option 1: a longest path.
> >Option 2: THE shortest path
>
> No, in roguespace those paths are of equal length.
> --
> David Damerell <damer....DeleteThis@chiark.greenend.org.uk> Kill the tomato!
> Today is Stilday, January - a weekend.

Yes, right. I forgot to mention that the Dijkstra algorithm finds the
shortest path with the "lowest cost".

Cheers,
-
/\+++/\
< agnas >
\/+++\/
 >> Stay informed about: Finding the Best Path 

Gamer_2k4 a écrit :
> On Jan 28, 4:45 pm, tyreciu... RemoveThis @yahoo.com wrote:
>> There are two potential solutions. The simpler one by far is to weight
>> diagonal movement slightly higher (or even \sqrt(2)) than orthogonal
>> movement. The more complex one is to break ties in favor of orthogonal
>> movement.
>
> Thanks. I made the change within about a minute; I have no idea why I
> didn't think of this before.

I had faced the same issue as you before when implementing a djikstra,
but it was much more puzzling for me because I had been working up to
now on another project that used A* as a path finder and they didn't
have such issue. I found that the heuristic choice in A* will have quite
a lot of effect on the solution chosen when you have multiple solutions
with the same cost.

So, the idea is to have a grid with an infinite norm movement costs as
you have currently (all directions cost 1) but implement A* with a sqrt
type norm as the heuristic used. You should get nice paths that look
like bresenham lines in the open rooms with that.
 >> Stay informed about: Finding the Best Path 

In article <479f2f8a$0$29454$426a74cc@news.free.fr>,
chris.cavalaria.RemoveThis@free.fr says...
> Gamer_2k4 a écrit :
> > On Jan 28, 4:45 pm, tyreciu....RemoveThis@yahoo.com wrote:
> >> There are two potential solutions. The simpler one by far is to weight
> >> diagonal movement slightly higher (or even \sqrt(2)) than orthogonal
> >> movement. The more complex one is to break ties in favor of orthogonal
> >> movement.
> >
> > Thanks. I made the change within about a minute; I have no idea why I
> > didn't think of this before.
>
> I had faced the same issue as you before when implementing a djikstra,
> but it was much more puzzling for me because I had been working up to
> now on another project that used A* as a path finder and they didn't
> have such issue. I found that the heuristic choice in A* will have quite
> a lot of effect on the solution chosen when you have multiple solutions
> with the same cost.
>
> So, the idea is to have a grid with an infinite norm movement costs as
> you have currently (all directions cost 1) but implement A* with a sqrt
> type norm as the heuristic used. You should get nice paths that look
> like bresenham lines in the open rooms with that.

Breaking ties in favour of orthogonal movement is pretty easy to
implement, though, even if you are using the basic Dijkstra algorithm.

- Gerry Quinn
--
Lair of the Demon Ape (a coffee-break roguelike)
<http://indigo.ie/~gerryq/lair/lair.htm>
 >> Stay informed about: Finding the Best Path 

On Jan 29, 4:06 pm, Christophe Cavalaria <chris.cavala....DeleteThis@free.fr>
wrote:
> Gamer_2k4 wrote:
> > http://roguebasin.roguelikedevelopment.org/index.php?title=Quick_Path...
>
> I've checked that page, and it looks like an implementation of Dikstra
> for me That is, if the stack where you push tiles for later use is a
> FIFO and not a LIFO. I guess it has to be or else I don't think the
> algorithm would work anyway.

I don't actually use a stack in my implementation of the algorithm. I
have two 2D arrays; one is a boolean array that keeps track of
obstructions, and the other is an integer array that holds the
distances from a certain point. I initially set all of those
distances to 999, then call my recursive function with the target
coordinates and 0 as the distance. The function does the following:
1. If the coordinates are off of the map, return.
2. If the current tile is obstructed, return.
3. If the distance on this tile is greater than or equal to the one
passed in as a parameter, return.
4. Set the distance of this tile to the one passed in as an argument.
5. Call this function recursively for the 8 tiles surrounding this
one, incrementing the distance by one.

I don't know if that's faster or slower than the stack, but I do know
that it makes more sense to me.

> Ok, here is a way to make it give you good looking paths without
> changing the core of the algorithm to a more complex one. You only need
> to alter the last step when you walk back the gradiant of the distances
> to the starting point. When you find multiple antecedants that are all
> at the same distance according to the movement cost, select the one that
> is closer to the starting point according to sqrt. If you don't like the
> look of the result in some cases, it might be worth it to run the
> pathfinder from the finish to the start point instead.

I have to run the pathfinder from the finish to the start; otherwise,
I'd just be starting at zero and picking a random tile with a move
cost of one more than the current tile, then moving to it (which is
A*, I think). Doing that could take me anywhere on the map, and it
would completely defeat the purpose of the previous step.

As for the distance check, it doesn't work, and here's why:
#####################
################PON.#
###################M#
###.....9ABCDEF.###L#
###....8.......G###K#
###...7.........HIJ.#
###..6..........#####
###.5...........#####
###4............#####
#.3.............#####
#2###################
#.10#################
#####################

0 is the start, P is the end. Notice that 9-F are all closer to the
destination than the path 2 tiles down (the one that goes directly to
the right door of the room). However, that's not the best path, at
least not visually (it's the same in terms of tiles traveled). And
like I said earlier, my pathfinder has no concept of rooms or doors;
even if it did, I'd need to calculate the path in segments, which
could get complicated. It's just much faster to favor orthogonal
movement, which was ultimately the solution I settled on (and it works
well, too).

--
Gamer_2k4
 >> Stay informed about: Finding the Best Path 

Quoting agnas <gustavorg.TakeThisOut@gmail.com>:
>On 29 ene, 10:20, David Damerell <damer....TakeThisOut@chiark.greenend.org.uk>
>>That's not the issue here; in roguespace, Gamer2k's awkward paths _are_
>>equal-shortest to the preferred ones.
>Are you saying that using the Dijkstra algorithm the resulting path
>will be the number 1option below???+
>Option 1: a longest path.
>Option 2: THE shortest path

No, in roguespace those paths are of equal length.
--
David Damerell <damerell.TakeThisOut@chiark.greenend.org.uk> Kill the tomato!
Today is Stilday, January - a weekend.
 >> Stay informed about: Finding the Best Path 

Gamer_2k4 wrote:

>
http://roguebasin.roguelikedevelopment.org/index.php?title=Quick_Pathf...ing_in_

I've checked that page, and it looks like an implementation of Dikstra
for me That is, if the stack where you push tiles for later use is a
FIFO and not a LIFO. I guess it has to be or else I don't think the
algorithm would work anyway.

Ok, here is a way to make it give you good looking paths without
changing the core of the algorithm to a more complex one. You only need
to alter the last step when you walk back the gradiant of the distances
to the starting point. When you find multiple antecedants that are all
at the same distance according to the movement cost, select the one that
is closer to the starting point according to sqrt. If you don't like the
look of the result in some cases, it might be worth it to run the
pathfinder from the finish to the start point instead.
 >> Stay informed about: Finding the Best Path