Moving algorithm

We need SUBJECTS (even the craziest ones are accepted).
CLARIFICATION: Algorithms for reaching one point from another
with overcoming (bypassing) obstacles.
PS More SUBJECTS.
PSS Write just like that, you want to communicate with monsters (and not so much) ZX WORL, yes.
In advance grateful.

With the BEST WISHES to you, ALL !!!

Bye!

We need SUBJECTS (even the craziest ones are accepted).
CLARIFICATION: Algorithms for reaching one point from another
with overcoming (bypassing) obstacles.
PS More SUBJECTS.

Once I was in a museum and there on an old, old stone an ancient man carved that
Sunday March 29, 1998 right at 13:47, Dmitry Kohno wrote All:

DK> with overcoming (bypassing) obstacles.

And immediately teleport the object from (*) A in (*) B and it hardly wastes time
and is original :))) And most importantly, it’s dry! :))

DK> With the BEST WISHES to you, ALL !!!

Wiz zE BeSt WisHeZ 2 U!
-=JoCkeR/OmEga HaCkErS Grp/1998year=-

DK> PS More SUBJECTS.
DK> PSS Write just like that, you want to chat with monsters (and not so much) ZX
DK> WORL, yes.
DK> Thanks in advance.
Here is the Mednonogovsky version:

----------------------------------------------------------------------------
Area: ZX.SPECTRUM (ZX.SPECTRUM: formed 01/31/1998)
Topic: For game makers who do not read ZX-Format...
----------------------------------------------------------------------------

=== Cut ===

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

Somehow, I remember, still 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 enough to know the basics of BASIC and what two-dimensional arrays are.

The task of finding the shortest path
between certain points A and B on the playing field with randomly placed 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 layoutboards),
based on no less number of different methods involved in connecting
two contacts with a 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 sizearray
of the playing field P(MxN).
2. Each element of the working array
R(i,j) is assigned a certain value
in the fields 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 passable, 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.
3. Stage "Propagation" waves." 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 line-by-line scanning
of the entire array, increase Ni by 1.
8. IfNi>Nk, then the route search is considered unsuccessful. Exit the program.
9. Go to point 5.
10. Stage of constructing a travel route. 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
some window wherestarting
and ending points. For example, in "UFO-2. Devils of the Abyss" with a field size of 64x64, work is carried out only with part of the field 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 passable, then
R(i,j):=254;
c) If the field P(i,j) is 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) andWe assign it an initial value of 0.

REM**> The stage is so named because filling the working array really resembles a wave. 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 some reservefree memory, it’s a good idea to remember at each
previous iteration the coordinates of the points included in the last wave. Then
points 5-6 will be reduced to viewing 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 as follows 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 of R(i+1,j):=Ni+1;
c) in the rest in 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 assembler 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 calling
R(i-1,j) does not make sense and can lead
to data corruption and a computer freeze. I
recommend in point 1 to create 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 modifyalgorithm.
How? Think of it yourself).

9. Go to point 5.

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

10. Stage of constructing the movement route.
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
is stronglyfalls.

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

REM**> Enter the coordinates of the route into such an intermediate list It makes sense if you have several heroes moving at the same time, and memory is allocated only for one working array R. Or if
space for R is allocated in a certain general area that 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 - large amount of required memory and notthe highest speed of finding the path. In "UFO-2", under the conditions listed above, finding a path can take up to 1/10 of a second.
This, of course, is acceptable for turn-based
strategies and logic games, but is difficult to use 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. Required somewherethe greatest
speed of calculations to the detriment of quality,
somewhere - the smallest number of turns,
somewhere - it is necessary that the route must pass through some key
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
V.I. Lenin, spoken by him at the III Congress of the
VLKSM: “Study, study and study - that is
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 ===

With The Best Wishes. [TEAM Speccy-r00leZ] [TEAM X-fILes]
[TEAM ┼he Pr0d!9Y] MaGeLan.