I've got a maze generated by filling some blocks in a rectangular array.

Some of the mazes are very sparse (almost no blocks filled) whilst others
are quite dense, and others are in between.

I've got an algorithm for finding the shortest path between any two points,
but it is very greedy, especially since most of the paths tend to be short.
It starts at the start point and recursively calculates the distance to each
connected point in the maze, then goes to the end and traces backwards.

Is there a better way of doing this (paths don't have to be absolutely the
shortest, just reasonable) ?

Noé Falzon wrote:

This is not a good method in this case.
1 ) It can fail, like you said.
2 ) It doesn't find the shortest path
3 ) There are better ways to do this, if we can see the whole map.

Your method is good if we can't see the whole map. And we are supposed
to find exit or something else inside a labyrinth, where walls are only
1 block thick.

Malcolm wrote:

I like this one:

http://www.roguelikedevelopment.org/...Droogendijk%20[gin@binky.homeunix.org].txt

Or go to:
http://www.roguelikedevelopment.org/...ment/index.php

And select "AI" and then "Quick Pathfinding in a Dungeon - Pieter
Droogendijk".

It only calculates the distance for as many steps as it is required to
get to the target point. However it calculates distance to all
directions, so it does some unneeded work. But it should be pretty fast
anyways.

"Malcolm" <malcolm@55bank.freeserve.co.uk> wrote in message news:bhnh6v$17r$1@newsg3.svr.pol.co.uk...
Have a look at Dijkstra's shortest path algorithm; if you want a 'reasonable'
path you could start this algorithm from both the start and endpoint
sumltaneously and stop when the 'fronts' intersect.

kind regards,

Jos

On Sun, 17 Aug 2003, Malcolm wrote:
I'm surprised that nobody (except maybe Aggro's URLs) has yet mentioned
the A* [A-star] algorithm. It's the classic path-finding algorithm, and
a quick Google for '"A star" tutorial' should get some stuff.

Basic algorithm, from memory:

Create a set of "interior" points, initially empty.
Create a set of "frontier" points, initially containing only the
starting-point.
Each 'point' has a 'parent' that is also a point. The parent of
the starting-point is itself (or NULL, or whatever).
Design a "distance to goal" heuristic; for example, the Euclidean
distance between point X and the goal.
Define a "distance to starting-point" function equal to the
number of "parent" links between point X and the starting-point.
Define the "total distance" heuristic EST(X):
EST(X) = distance-to-goal(X) + distance-to-starting-point(X).

For the point X in the "frontier" set with the minimal
distance-to-starting-point(X),
For each neighbor Y of X,
If Y is not in either set yet,
put Y in the frontier set,
and set parent(Y) = X.
If Y is in the frontier set, but EST(Y) > EST(X)+1,
set parent(Y) = X.

Repeat until parent(goal) has been set to some point.
Follow the "parent" links backwards from the goal to find
the resulting path.

HTH,
-Arthur

In article <1fzu32v.1w0ya3f1q9yxmoN%PASDEPUBnoe.falzon@tiscal i.fr>, PASDEPUBnoe.falzon@tiscali.fr (=?ISO-8859-1?Q?No=E9_Falzon?=) wrote:
It's the standard 'wavefront' (AKA Dijkstra) algorithm. You can add
heuristics to tell it to try certain directions first (look up A*) - in
simple mazes this should be faster most of the time, although wavefront
should give the least bad worst case.

For finding 'reasonable' paths where there are large open spaces, a
heuristic approach is probably best. For a Pacman-style maze with
narrow passages and many walls, wavefront is probably the best (and it
won't be confused by the wrap-around, as a direction-based heuristic
will be...

Try wavefront first, you may be surprised to find it is fast enough for
your application. If multiple paths must be found in the same maze, or
a slightly varying maze, all bets are off, because you want to combine
information between runs.

Gerry Quinn
--
http://bindweed.com
Screensavers and Games for Windows
Download free trial versions
New screensaver: "Hypercurve"

In article <Xns93DB51DC0D87Cnewspubwuggyorg@217.32.252.50>,
Ian Woods <newspub@wuggy.org> wrote:
...
Yeah, you're right. I like that approach.

-Mike
--
http://www.mschaef.com

On Sun, 17 Aug 2003, MSCHAEF.COM wrote:
Unless it's not. ;-)

If I understand what you wrote correctly, you're looking at a maze like
this one:

### ###
# # #
# # # #
# #
# ### #
# # #
### ###

and then iteratively "filling in" all cells which are surrounded on
three or more cardinal sides by walls:

### ### ### ### ### ### ### ### ### ###
#X# # ### # ### # ### # ### #
# # # # #X# # # ### # # ### # # ### # #
# # # # #X # ##X # ### #
# ### # #X### # ##### # ##### # ##### #
#X# # ### # ### # ### # ### #
### ### ### ### ### ### ### ### ### ###

Now you have no more cells to fill in, yet there is no unambiguous
path from one side to the other (and you haven't detailed any
algorithm that would find one of the available paths).

Yes, if you create a spanning tree of the graph before
applying this algorithm *to the tree*, you will get a path.
But then it won't necessarily be the shortest path, even
if you did start with a minimal spanning tree.

Alternately, you could perform this "trimming" algorithm on
the original maze, and then find the minimal spanning tree
of *that* graph, and then "trim" the tree one more time.
This will produce a short path, although I am not satisfied
that it is necessarily the *shortest* path.

-Arthur

In article <Pine.LNX.4.55L-032.0308181506120.6237@unix44.andrew.cmu.edu>, "Arthur J. O'Dwyer" <ajo@andrew.cmu.edu> wrote:
If you like.

But wavefront is easier to understand and implement (in fact I think
the OP may already have done so). Why worry about something more
complicated unless you are likely to need it?

Gerry Quinn
--
http://bindweed.com
Screensavers and Games for Windows
Download free trial versions
New version of popular arcade game 'Bubbler'

Ian Woods wrote:

<snip>
Ooh... looks like an ALife problem.

Rules:
if alive_before, alive
if neighbors > 6, alive



--
Corey Murtagh
The Electric Monk
"Quidquid latine dictum sit, altum viditur!"

In article <1061260804.360135@radsrv1.tranzpeer.net>,
Corey Murtagh <emonk@slingshot.co.nz.no.uce> wrote:
...
Yes, the algorithm is based on a cellular automata.

There's a fairly active field of study surrounding what such
algorithms are capable of. One interesting example is this:

http://rendell.server.org.uk/gol/tm.htm

It's a Turing machine specified entirely as a cell formation in
Conway's game of life. It had been established as a theoretical
possibility long before it was actually done.

-Mike
--
http://www.mschaef.com

In article <Pine.LNX.4.55L-032.0308181454290.6237@unix44.andrew.cmu.edu>,
Arthur J. O'Dwyer <ajo@andrew.cmu.edu> wrote:
...
It seems like you did. :-)

I guess it's still possible to make a mistake in the traversal.

I suppose that the promise made by the algorithm is somewhat weaker
than a true solver.

-Mike
--
http://www.mschaef.com

"Gerry Quinn" <gerryq@indigo.ie> wrote in message
fast machine. I wanted to know if there was an algorithm I was missing.
BTW how was the original Pacman path-finding implemented?

In article <bhtnbh$38b$1@news7.svr.pol.co.uk>, "Malcolm" <malcolm@55bank.freeserve.co.uk> wrote:
AFAIK it didn't involve path-searching, just different rules like
'Turn to move towards player', or 'Turn randomly'. There is literature
around if you search.

Gerry Quinn
--
http://bindweed.com
Screensavers and Games for Windows
Download free trial versions
New version of popular arcade game 'Bubbler'