For game makers who don't read ZX-Format...

28 Jan 98 18:19, Sanya Ershov reported All about {Implementation of the search algorithm for
paths}:

SE> Tell me, plz, how to implement the wave algorithm for searching
SE> paths (when you put numbers on the “virtual map”). You can

SE> P.S. If anything, forgive the teapot!

From "ZX-Format #6" August 1997

=== Cut ===

Building the shortest route.
(c) B.C.Medononogov

Somehow, I remember, back in The game "UFO-1" conveyed a wish to those who want to become a good programmer, to raise, raise and once again raise their educational level. Well, from the pages of one very respected publication, a reader came up with the following thought (I don’t remember verbatim): “I’m a dark person, but I’m a good coder. That means I’m already a good programmer.”
This article is an attempt to dispel this deep misconception. First of all, it is addressed to those who are engaged in creating games and to those who are haunted by the thought: “What’s inside?” To understand it, it is sufficient to know the basics of BASIC and what
two-dimensional arrays are.

The task of findingthe shortest path between certain points A and B on the playing field with randomly located obstacles is typical, first of all, for tactical and strategic games that are popular today. As a subtask, it can arise in almost any game - RPG, quests, logic (a typical example is "Color Lines", by the way, making the next version of such a toy after this article is a piece of cake). Why do you need to look for the shortest route? In some games, for example "UFO-2", "Laser Squad", the number of time units spent depends on the length of the route - the more optimal the path is found, the faster the warrior will reach the goal. And, for example, in “Color Lines”
the length of the route is not specified by the rules,
only the very fact of the possibility
or impossibility of moving the ball matters. But
in this game it will be more pleasant to look at if
the ball immediately goes where it needs to go, and does not
mysteriously parade across the entire game
board.

The solution to this problem came to us from such a far, it would seem, from games area
as electronics. Namely, the layout of printed circuit boards (does everyone know what this is?).
There are a large number of tracers (programs for board layout),
based on no less number of different methods involved in connecting
two contactsa single conductor. But we
will consider only one of them, the simplest
(and therefore the most reliable and the most
popular) - the wave tracer.

Let's set the wave tracer
a task in terms of the game
we are developing:
Yes playing field P(MxN), where M and N, respectively, are the vertical and horizontal dimensions of the field. Simply, it is an array of size MxN (DIM P(M,N)). Each cell of the playing field (array element) can have a large number of properties at your discretion, but for us only one thing is important - its passability (or impassability). How it is determined is up to you. Further: there is a certain starting point where the hero of your game is, and an end point where he needs to get to. Let's agree for now that he can only walk in four directions (which the classical wave method requires of us) - right, left, forward, back. It is necessary to move the hero from
the starting point to the finish in the least number of moves, if such movement is at all possible.

The algorithm for finding the shortest route
between two points for such a task
is quite simple:

1. First, you need to create a working array R(MxN), equal in size to the playing field array P(MxN).
2. Each element of the working array R(i,j) is assigned a value
infield P(i,j) according to the following rules:
a) If field P(i,j) is impassable, then
R(i,j):=255;
b) If field P(i,j) is passable, then
R(i,j):=254;
c) If field P(i,j) is the target
(finishing) position, then R(i,j):=0;
d) If the field P(i,j) is the starting position, then R(i,j):=253.
3. Stage of “Wave Propagation”. We introduce the variable Ni - the counter of iterations (repetitions) and assign it the initial value 0.
4. We introduce the constant Nk, which we set equal to the maximum possible number of iterations.
5.Look through the working array R line by line (i.e., organize two nested loops: by array index i from 1 to M, by array index j from 1 to N).
6.If R(i,j) is equal to Ni, then neighboring elements R(i+1,j), R(i-1,j),
R(i,j+1), R(i,j-1) are looked through according to the following rule (as an example, let’s consider R(i+1,j)):
a) If R(i+1,j)=253, then go to point 10;
b) If R(i+1,j)=254, the assignment R(i+1,j):=Ni+1;
c) In all other cases, R(i+1,j)
remains unchanged.
We proceed similarly with the elements
R(i-1,j), R(i,j+1),R(i,j-1).
7. Upon completion of the line-by-line scan
of the entire array, we increase Ni by 1.
8. If Ni>Nк, then the route search is considered unsuccessful. Exit the program.
9.Go to point 5.
10.Building stageroute of movement. We assign the variables X and Y the values of the coordinates of the starting position.
11. In the vicinity of the position R(X,Y) we look for
the element with the smallest value (i.e. for
this we look through R(X+1,Y), R(X-1,Y),
R(X,Y+1), R(X,Y-1).The coordinates of this
element are entered into the variables X1 and Y1.
12. Move the object (whoever you have - a robot, an aquanaut, Win-no-Pooh) across the playing field from position [X,Y]
to position [X1,Y1]. You can
preliminarily enter the coordinates X1,Y1
into some array, and only after finishing
constructing the entire route, start moving the hero on the screen).
13. If R(X1,Y1) = 0, then go to step 15.
14. We assign X:=X1,Y:=Y1.
Go to step 11.
15.That's it!!!

For those who understood everything right away, I recommend not to read further. For normal people
I will repeat it again with comments and explanations:

1. First you need to create a working
array R(MxN), equal in size to the
playing field array P(MxN).

REM**> So far, everything is simple. In BASIC - just
the command DIM R(M,N) In assembler -
something like "_R DEFS _M*_N". The playing field is large, it makes sense to select a certain window where the starting and ending points fall. For example, in "UFO-2. Devils of the Abyss" with a field size of 64x64, work is carried out only on a part.fields are 32x32 in order
to limit the number of calculations.

2. Each element of the working array
R(i,j) is assigned a certain value depending
on the properties of the element of the playing
field P(i,j) according to the following rules:
a) If the field P(i,j) is impassable, then
R(i,j):=255;
b) If the field P(i,j) is traversable, then
R(i,j):=254;
c) If the field P(i,j) is the target
(finishing) position, then R(i,j):=0;
d) If the field P(i,j) is the starting
position, then R(i,j):=253.

REM**> Also without complications. Walk through the playing field array P, determine whether the current cell is passable/impassable, and accordingly write the number 254/255 into the cell of the array R. Upon completion, enter 253/0 into the start/stop position. There are several ways to set
the properties of a playing field element. Two specific examples: in "UFO1/UFO2" a byte array of properties of landscape sprites is organized, each bit has its own property, for example, the 7th bit is responsible for cross-country ability. In "Black Crow" it is made simpler - sprites with numbers from 0 to 31
are passable, older ones are not.

3. Stage "Wave Propagation". We introduce
the variable Ni - the counter of iterations (repetitions) and assign it the initial value 0.

REM**> The stage is named so because filling the working array really resembleswave. Please note that the propagation of the wave begins from the final point.

4. We introduce the constant Nk, which we set equal to the maximum possible number of iterations.

REM**> This is a very subtle point. Let's assume that between the beginning and the end there is an insurmountable obstacle, then the search for the path will come to a dead end and the program will go into a loop. To prevent this from happening, such a variable is introduced. Its value is selected experimentally. For example, in the same "UFO-2" even an aquanaut general, having 108 units of time and a lot of energy, will not be able to move more than 27 cells per turn. However, I still did Nk=64. In any case, with our method of solving the problem, Nk cannot exceed 253 (can you guess why?).

5. Line by line we look through the working array R (i.e. we organize two nested loop: by array index i from 1 to M, by array index j from 1 to N)

REM**> I think it’s clear how to do this
in BASIC. In assembler, I would not do two loops, but would do one, remembering that the array lines in memory are stored one after another and form a continuous chain of bytes.
Moreover, if you have a certain amount of free memory, it’s not bad to each
previous iteration remember the coordinates
of the points included in the last wave. Then
points 5-6 will be reduced toviewing only
these points, which will significantly increase
performance!

6. If R(i,j) is equal to Ni, then neighboring elements R(i+1,j),
(R(i-1,j), R(i,j+1), R(i,j-1) are viewed according to the following rule (as an example consider
R(i+1,j)):
a) if R(i+1,j)=253, then go to
point 10;
b) if R(i+1,j)=254, the assignment R(i+1,j):=Ni+1;
c) in other cases R(i+1,j) remains unchanged.
We proceed similarly with the elements
R(i-1,j),R(i,j+1),R(i,j-1).

REM**> A few points for assembly language programmers. Because We are looking for a match of array elements with only one number (Ni), then to achieve the highest search speed it is recommended to use the CPIR command. Second note: with
fixed dimensions of the playing field, the addresses of neighboring elements can not be calculated using complex formulas, but can be specified by numerical offsets (for example, with a field of 32x32
the offsets of four neighboring cells are equal to
-32, -1, +1, +32). The third note, important for everyone: taking into account edge effects (meaning elements located
on the boundaries of the array) can take a lot of time during calculations. Indeed, if, for example, i=1 (or 0 in C), then accessing R(i-1,j) does not make sense and can lead to data corruption and a computer freeze. I
recommend in point 1create a working
array of size not M by N, but (M+2)x(N+2)
and give all boundary elements a value
255 (impassable). It takes a little
more memory, but it is easier to program, and
calculations will go faster. That's what I did
in "UFO-2".

7. Upon completion of the line-by-line scanning
of the entire array, we increase Ni by 1.

8. If Ni>Nk, then the route search is considered unsuccessful. Exit the program.

REM**> I deceived you a little. Mathematically, the exact conditions for an unsuccessful search sound like this: “If at the current step not a single element R(i,j) equal to Ni was found,
then the route connecting the two points does not exist.” You can use
this rule if you like absolute
accuracy (in this case the Nk parameter is not needed at all), but it seems to me that it is better to do one check at the end than a hundred at the search stage.
Yes, I almost forgot, the algorithm Wave propagation can be perfectly used for filling small figures of arbitrary shape. So, if you want to create your own Art Studio, and nothing comes to mind, you can use
this method (to do this, we throw out points
10-15 and slightly modify the algorithm.
How? Think for yourself).

9. Go to point 5.

REM**> That is, we continue generating the wave.

10. Route construction stagemovement.
Assign to the variables X and Y the values of the coordinates of the starting position.

11. In the vicinity of the position R(X,Y) we look for
the element with the smallest value (i.e. for
this we look through R(X+1,Y), R(X-1,Y),
R(X,Y+1), R(X,Y-1)). The coordinates of this
element are entered into the variables X1 and Y1.

REM**> The method of viewing neighboring elements
is similar to how it was done in step 6. If your hero knows how to walk diagonally, then you can include in the search also
four neighboring diagonal elements
that need to be viewed _first_ turn. The same, but a little more complicated, was done in
"UFO-2" (when considering diagonal
movement sections according to the rules adopted for most strategies, there should be no
interference with movement on the right or left).
Attention! This method of taking into account diagonal movements gives approximately 95% probability of finding the truly shortest route. In my opinion, this is quite enough. If you suddenly need the shortest path with a 100% guarantee, then already in point 6 you should
take into account the diagonal elements, taking into account the restrictions imposed by your game. The speed of wave propagation
in this case drops significantly.

12. We move the object across the playing field from position [X,Y] to position
[X1,Y1]. If you wish, you can pre-
enter the coordinates X1,Y1 into some array, and only after finishing constructing the entire route, start moving the hero on the screen.

REM**> Entering the coordinates of the route into such an intermediate list makes sense if you have both several heroes are moved, and memory is allocated only for one working array R. Or, if
space for R is allocated in a certain general area, which other subroutines can
use for their needs. By the way, you can remember not the coordinates themselves, which
in our example will take 2 bytes, but the codes
of the directions of movement, which is enough for one.

13. If R(X1,Y1) = 0, then go to the point 15.

REM**> Well, now we have reached the handle, i.e. to
the final point.

14. We assign X:=X1, Y:=Y1.
Proceed to point 11.

15. That’s it!!!

Isn’t it simple? To avoid any ambiguity, this issue of the magazine provides a simple example in BASIC. After watching
it, you will at least be able to repeat
"Color Lines".

Advantages and disadvantages of the method.

Advantages - simplicity, reliability, 100%
the shortest path (for the classic
method). Disadvantages - a large amount of required memory and not the highest speed of finding the path. In "UFO-2", under the conditions listed above, finding the path can be achieved in timeup to 1/10 of a second.
This, of course, is acceptable for turn-based
strategies and logic games, but is difficult to
suit for dynamic games. And about
the attempt to implement it in BASIC, I am generally
silent (except as an example).

Variations of the method.

Double wave - wave propagation
starts from both the final and the starting point, and the route is made up of
two sections - from the meeting points of the waves before the start and to the finish. Theoretically, it can
increase the search speed by 3-4 times.
But how in practice?
In the case of an acute lack of memory, for example, if you are planning not a game, but a
real board tracer on the Spectrum,
a truncated encoding
waves. Those. the first wave has the number 1, the second - 2, the third - again 2, the fourth - 1 and so on. The encoding of one element will require two bits (numbers 0/3 will describe the passable/impassable field). When searching for a route, we look for neighboring memory cells in the same order (... 1 1 2 2 1 1
2 2 1 1 2 2...). There can be no talk of any diagonal
movements.
In addition to the wave one, there are a relatively
large number of methods for searching
routes. Somewhere the greatest
speed of calculations is required to the detriment of quality,
somewhere the smallest number of turns,
somewhere it is necessary that the route must pass through somekey
points (no matter in what order). New tracing methods allow you to search for routes in which the path can pass at any angle (not only multiples of 90 and 45 degrees). Progress does not stand still!
Therefore, I would like to end the article with the words of V.I. Lenin, spoken by him at the III Congress of the Komsomol: “Study, study and study - that’s your main task!”

P.S. I would like to thank the teachers of St. Petersburg State Technical University (LETI) from the CAD department, who taught me all this, and I, as best I could, told you. Well, and once again I remind you that anyone who wants to become a real programmer should only go to this institute, straight to this department :-)

Always yours, Vyacheslav Mednonogov.

=== Cut ===

* Crossposted in RU.GAME.DESIGN
* Crossposted in ZX.SPECTRUM

Warm greetings, Glory!