Finding the Best Path

Quoting agnas <gustavorg DeleteThis @gmail.com>:
>On 29 ene, 13:36, David Damerell <damer... DeleteThis @chiark.greenend.org.uk>
>>No, in roguespace those paths are of equal length.
>Yes, right. I forgot to mention that the Dijkstra algorithm finds the
>shortest path with the "lowest cost".

Which is why the suggestion of slightly increasing the cost of diagonal
movement is a solution and discussion of algorithms is irrelevant.
--
David Damerell <damerell DeleteThis @chiark.greenend.org.uk> flcl?
Today is Gorgonzoladay, January - a weekend.
 >> Stay informed about: Finding the Best Path 

Gamer_2k4 wrote:

> 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).

That was exactly the situation I was thinking about. I bet the player cannot
see what the monster is doing in that case so that solution probably isn't
that bad anyway.

Besides, you can always explain that as the possibility the player might
decide to dig through the rock at that time so it might be a good idea to
stay close to the wall in case it happens. Don't underestimate the illusion
of intelligence that arises from randomness and implementation details :p
 >> Stay informed about: Finding the Best Path 

On Jan 28, 4:29 pm, Gamer_2k4 <gamer....DeleteThis@gmail.com> wrote:
> 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?

Do you have any way to introduce cost-based metrics into your
calculation? You could penalize directional changes, so that //-\
(which has 2 changes) is worse than /--- (which only has one change).

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

In article <2963e6c4-4fb3-40a7-a2ce-4e3047b4a889
@u10g2000prn.googlegroups.com>, tbarta DeleteThis @gmail.com says...
> On Jan 28, 4:29 pm, Gamer_2k4 <gamer... DeleteThis @gmail.com> wrote:
> > 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?
>
> Do you have any way to introduce cost-based metrics into your
> calculation? You could penalize directional changes, so that //-\
> (which has 2 changes) is worse than /--- (which only has one change).

Just favour orthogonal over diagonal movement. Since an orthogonal step
is shorter in Euclidean terms, this will automatically result in shorter
paths with fewer bends.

The more diagonal moves, the longer the Euclidean path, and the more
opportunity for bends.

- Gerry Quinn
 >> Stay informed about: Finding the Best Path 

On Mon, 28 Jan 2008 14:29:06 -0800 (PST), Gamer_2k4 <gamer2k4.DeleteThis@gmail.com>
wrote:

>I've been working on some pathfinding code for my game, and I'm
>running into a problem. A correct path is made, but it normally looks
>something like this:
>
>#################
>##.....89ABCDE.##
>##....7.......F##
>##...6.........GH
>##..5..........##
>##.4...........##
>##3............##
>12.............##
>#################
>
>It's functional, but the monster seems to go out of his way when
>getting to the destination. I know why this happens, so that's not
>the problem. The problem is that I want the path to look like this:
>
>#################
>##.............##
>##.............##
>##...6789ABCDEFGH
>##..5..........##
>##.4...........##
>##3............##
>12.............##
>#################

Note that the wall-hugging behavior of the first path actually gives a
greater impression of cautious intelligence. By lining up with the
opening on the far side before heading towards it, the monster opens
itself up to attack by an unseen foe down the corridor (maybe that's
what you want).

--
R. Dan Henry = danhenry.DeleteThis@inreach.com
If you wish to put anything I post on your website,
please be polite enough to ask first.
 >> Stay informed about: Finding the Best Path 

On Jan 30, 8:51 am, Christophe Cavalaria <chris.cavala....TakeThisOut@free.fr>
wrote:
> Gamer_2k4 wrote:
> > 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).
>
> That was exactly the situation I was thinking about. I bet the player cannot
> see what the monster is doing in that case so that solution probably isn't
> that bad anyway.

Well, monsters don't always have to move towards the player. Maybe
it's heading towards an item, chasing an enemy, or trying to escape
via the stairs. Then the player WILL see the anomalous movement and
wonder what's going on.

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