Virtual Worlds #01 31 декабря 1999

Программирование

Assembler - search path. Solution to the problem of "static" find the shortest route between two points.

           Pathfinding



           (C) TimeKeeper / MHCG



  Finding the shortest path - a very
interesting algorithmic problem. Its scope is very
extensive: the strategic and logic games (turn-in
real-time), system
program (PCB router), etc. For us in
Currently, the most interesting
algorithms that can be used in games. I am inclined to share 
all these algorithms on two categories: static and dynamic.



  Dynamic search algorithms
ways have to work very
fast and correct way to
Depending on the dynamic changes in the landscape (movement
other objects, the emergence of new
obstacles, the disappearance of the old ... ). Such algorithms 
are used for strategic games where actions occur in real time. 
One of the these algorithms were successfully

B. Mednonogovym implemented in
"Black Crow".


  Static algorithms are used to turn-based strategy,
PCB layout software
and other areas where needed
accuracy and does not necessarily
speedy delivery (for example
can serve as a UFO-II).


  The dynamic algorithm performs much faster than static, but 
have low accuracy, while the static inferior in speed, but have 
100% accuracy. 


  Recently I faced the task of creating a static shortest path 
algorithm for the gaming card size

128 * 128 fields. Then I was known only one algorithm. The 
exact title I do not remember, but he acted about

as follows: Suppose we have
two-dimensional array KARTA (x, y) -
Map size X * Y, which will build the path. Establishments
two additional one-dimensional
array of size x * y: INDEX
(X * y) and PATH (x * y).


  The essence of the algorithm is to
that at each step we
See where to go from
cells, in which we could get to the previous step and, if
These cells are absent in the array
INDEX, we add them back
and an array of PATH write accordingly path - the number (or
coordinates, it will be someone like
convenient) cells, from which we
fall into the one recorded in
array INDEX.


  The algorithm finishes its work in one of two ways:
Either we have reached the desired cell
or we have nowhere else to go,
ie, we have recorded in the array INDEX
all the cells, which can be reached from the initial and among 
them was not required. Clearly,

that in the second case, the path we are not
found at all.


  We now show that if we
found a way, it is the most
the shortest and the shortest path does not exist. Generally 
speaking, This follows from our algorithm.

At each step, we looked at
which cells can go from those
in which we could come to
previous step and add them to
array INDEX, if there is not
was. Hence, as a result we
have the shortest path, ie
because if there were a shorter path, it would mean
that before the cells of the target can be reached
in fewer steps and hence
she already would be contained in an array
INDEX, which contradicts our
algorithm.


  Pretty good and understandable
algorithm, but look at how we
able to implement it in practice:


  For the work we ponadobyatsya
Two working array of dimensions
X * Y, and this is neither more nor less, and
3 * X * Y bytes of RAM, plus a buffer
for storing the found path.
If the card has a small razmeroy,
it is more or less acceptable, but, as mentioned above,
static algorithms are primarily used for incremental
strategies or PCB
boards. If you take the card size
128 * 128, then for a game that still all right (although it is 
generally small), but for printing Motherboard is completely 
unacceptable - A maximum of five buildings chips in length with 
a class of routing no higher than third. But then

128 * 128 - it is 16384 bytes for
Card + 3 * 128 * 128 = 49152 bytes
Array search for the path, and even buffer to store the path.


  Generally speaking, the size of the working
arrays can be reduced and to take
their number is equal to the number of cells on the map, which 
can walk, but it's hardly solve

problem.



          Algorithm 2.


  In fact, it is the same
algorithm optimized me
the criterion of minimizing the buffer memory is used by 
(although the speed is not displayed

the best way).


  We have stored in memory array
with dimensions equal size
card. Each byte of this array
responsible for one square on the map
and has the following bit-wise
layout:


Bits: 7 6 5 4 3 2 1 0

                        INDEX

                        PATH
not used-MASKSTEP
favor-TARGET
is INPUT


INDEX - Replacement of the array of the previous algorithm and 
takes the following values:


= 0 if the cell was not added to the array.

= 3, if a cell is already entered in the
array.

= 2, for cells of data entered into the array at the current 
step. 

= 1 for listed in the previous step.

PATH - two bits of direction. Contain a code indicating
of a cell, we got this:


          0 - right

          1 - top

          2 - left

          3 - bottom

MASKSTEP - bit contains 0, if the cage you can walk
(Ie, if it is passed), and
1 - otherwise.

TARGET - contains 1 if it
cell-target.

INPUT - contains 1 if it
cell source.


  With this approach, a map
128 * 128 will need an array of 16384 bytes, which is just
equal to the volume of one page of memory.

The algorithm:

 0. Create a working set size XLEN * YLEN.

 1. We are looking for in an array of cells with
INDEX = 1. If these are absent, then go to step 6.

 2. For each matched cells
check to see where you can go, so
e. check the box to the left, top, right, bottom, and if they
INDEX = 0, and MASKSTEP = 0, then write back INDEX = 2, and 
PATH: 


    2 - for the cell to the left

    3 - - / / - top

    0 - - / / - right

    1 - - / / - bottom

3. If some of the cells tested in paragraph 2, we find cell 
target, ie the one in which TARGET = 1, then go to step

7.

4. Now consider the entire array, and
replace INDEX = INDEX = 1 to 3,
INDEX = 2 INDEX = 1.

5. Go to step 1.

6. Path does not exist, stop.

7. So we found the cell-target
Now create a buffer path:

 a) Put the pointer on kletkutsel.

 b) Add to clipboard path number contained in a cage,
which is a pointer to the field
PATH.

 c) Shift the pointer on the cell
from which we got to the one on
which now is a pointer.
All this is repeated until,
until we reach kletkiistochnika, ie one in which
INPUT = 1.


  As you probably noticed,
This algorithm can walk
only in four directions
horizontally and vertically, you
ask: "Why?". Just when I developed this algorithm,
in front of me was just such a
problem, but nobody prevents you to withdraw under the 
direction of three bits (in our version does not use the 
seventh bit) and make the possibility of moving in eight 
directions. Further, the algorithm can still be optimized, if 
you throw out paragraph 4. Done it is very simple. As mentioned 
above, INDEX takes one of four values:


0 - the cell has not yet been tested
3 - already checked
1 and 2 - are used to determine in which cells we
might fall in the previous step
(1), and in what we can get on
current (2).


  Further, in all cells INDEX = 1
replaced INDEX = 3, INDEX = 2
for INDEX = 1. Thus we
prepare a working card to the
the next step. Doing so:
introduce two new variables
VAR0, VAR1 (Originally VAR0 = 1,
VAR1 = 2). In the first paragraph shall
search for cells with INDEX = VAR0 and
immediately assign them to INDEX = 3.
Now in the fourth paragraph, instead of changing the indices
on the map, simply swap
variables VAR0 and VAR1,
that much faster.

So:

0. Create a working set size XLEN * YLEN. and assign
VAR0 = 1, VAR1 = 2.

1. We are looking for in an array of cells with INDEX
= VAR0. If these are absent,
then go to step 6.

2. For each matched cells:

  a) assign INDEX = 3.

  b) check where to go,
ie check the box to the left,
top, right and bottom and, if
They INDEX = 0 and MASKSTEP = 0, then
Make an INDEX = VAR1, and
PATH:


      2 - for the cell to the left

      3 - - / / - top

      0 - - / / - right

      1 - - / / - bottom

3. If some of the cells tested in paragraph 2, we find 
kletkutsel, ie the one in which TARGET = 1, then go to step 7.


4. Change the value of variable
VAR0 and VAR1 places: TEMP: = VAR0,
VAR0: = VAR1, VAR1: = TEMP.

5. Go to step 1.

6. Path does not exist, stop.

7. Thus we have found cell-target and
need to create a buffer path (see
above).


  Paragraphs 1 and 2 are better connected, ie
is, if you find a cage, then immediately
We perform for her all of the
paragraph 2. Also, it is better to check the cage for the 
presence of TARGET = 1, not to make unnecessary

cycles.


  Still, for this example, we can reduce the buffer used
program under the dynamic map is twice that in principle,
entail a reduction in
processing speed. For this
We use only four
bit: 2 bits - INDEX, 2 bits -
PATH. And define the TARGET and
INPUT will be given coordinates (or
address). You can go to the next cell or not, we will determine 
on the card itself. 


  Generally speaking, the options here
very much and it all depends on your imagination and abilities, 
so that, go for it.