Re: Plain English Djikstra - help??

At Tue, 09 Oct 2007 11:07:01 -0700,
Brigand wrote:

I think where I am getting tripped up is the whole 'weighting' thing.
On a real-life map, thsi makes sense - there are discrete distances
associated with each node-path. But on a graph, each node is exaclty 1
(or 1.44 in the case of diagonals) away from it's nearest neighbor. Do
you assign some high number to the node if it's blocked?

Dijkstra uses a variation on a flood-fill algorithm to count the distances
from your starting point. Let me first explain how the flood-fill
algorithm works (it's also useful in map generation algorithms and a lot
more, so it's good to know it).

== Flood fill ==

You have some map and a point on that map. You want to fill the area
surrounding that point. You do it by filling the starting square, then
filling all four (or eight) its neighbours, then filling their neighbours,
etc. The problem is you can only fill one square as a time, so you need
to remember the to-be-filled squares somehow. You can use either a queue
or a stack. We will use a queue, and I will explain the difference later.

A queue is a data structure that allows you to add squares to it (insert)
and remove them (remove). The distingusihg feature of queue is it's first-in,
last-out (FILO) order. This means, that the most recently added squares
will be removed last, just like a queue in a shop or cinema.

We initialize our queue by putting the starting square in it (and filling
that square). We will repeat our algorithm as long, as there is at least
one sqauare in the queue. When the queue is empty at the end of a single
iteration of our algorithm, we stop.

The itearions are as follows: first, remove a square from the beginning of
the queu. Then take all the non-filled, non-wall neigbouring squares, fill
them and insert them at the end of teh queue. Rinse and repeat.

Exmaple:
(lowercase squares are non-filled, uppercase are filled, # is wall)

#### Queue: G
#ab###
#cd#e#
#fGhi#
######

remove G,
fill D, insert D,
fill H, insert H
fill F, insert F,

#### Queue: FHD
#ab###
#cD#e#
#FGHi#
######

remove D,
fill B, insert B
fill C, insert C

#### Stack: CBFH
#aB###
#CD#e#
#FGHi#
######

remove H
fill I, insert I

#### Stack: ICBF
#aB###
#CD#e#
#FGHI#
######

remove F
remove B
fill A, insert A

#### Stack: AIC
#AB###
#CD#e#
#FGHI#
######

remove C
remove I
fill E, insert E

#### Stack: EA
#AB###
#CD#E#
#FGHI#
######

remove A
remove E
stop

Using a queue makes it fill the squares closest to the starting point
first. If you used a stack instead, it would first build a path as far
as possible, and then turn and backtrack when hitting any walls or filled
areas. Using a queue is usually more memory-efficient.

Now that we have our flood-fill algorithm, we can make it count distances.
The idea is simple -- each time you pick a square, it already has
a distance computed. When you fill its neightbours, you just give them
the distance "one step" larger (where the step is the cost of movement
between teh squares). Our example would give us this distance map:

####
#32###
#21#3#
#1012#
######

If the wieghts of steps are not all equal, you need an additional rule:
you also "step" into a square if it's already filled, if only the new
distance you'd put onto it with that step is smaller than the distance
already on it. For example, let's say you somehow have map like this:

3#2
4#3
564<---

and you just removed from the queue the square marked with an arrow.
Since you must re-fill and insert into the queue the square marked with
6, because this operation marks it with 4+1=5<6.

Once we have our "distance map", we can find the shortest way from any
point on the map to the starting point by just "going uphill", that is,
moving to the square with the lowest number each step.

--
Radomir `The Sheep' Dopieralski <http://sheep.art.pl>
() ascii ribbon campaign - against html e-mail
/\ <www.asciiribbon.org> - against proprietary attachments
.

Relevant Pages

  • Re: Image Distort Question
    ... probably the best is to use a conformal map of a ... >> unit disk to a square using, say, the usual Schwarz-Christoffel ... and reflections of course) conformal map from the square to the ...
    (comp.graphics.apps.gimp)
  • RE: Calibration curve
    ... I hop eyou used the sum of the square of the distances to get the error. ... Signa is the width of the normal distribution curve. ... The distance becomes your error. ...
    (microsoft.public.excel.misc)
  • Re: Perspective not quite correct?
    ... Any point in space gets mapped to the wall using a light ray from that point ... the square in the top left corner would be the same size as the one ... Imagine you have a sheet of glass in front of you and you traced the image ... If you look at one of the little checkers at a corner, it has a distance ...
    (microsoft.public.win32.programmer.directx.graphics)
  • Re: can anyone tell me a little about this puzzle - quartering squares & the pythagorean the
    ... approximation to the diagonal of a square, constructed by dividing the ... "saves" any distance traveling between opposite corners versus ... you've traveled a distance of two. ...
    (sci.math)
  • Re: Help with cave map generator
    ... wanted a map generator that produced open cave spaces, ... small chance of that square being dug (chance depends on cave style ... After doing some reading I guess this would be ...
    (rec.games.roguelike.development)