ZX Format #06 29 июля 1997

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

Programmers - AI on B. Mednonogova. A detailed description of the "wave of the algorithm" trace (automatic calculation of optimal) path, with an example implementation at Basic.

Construction kratchayshego marshruta.

music by DNK
(C) B. Mednonogov
_______________________________



 HOW, I remember, back in the game, "UFO-1,
slipped pozhelanie to those who want to
stat good programmistom, povyshat,
povyshat and still raz povyshat your obrazovatelny level. Ha 
that with a very stranits uvazhaemogo izdaniya made chitatel 
with the following thought (not literally remember): "I'm a 
dark person, but the encoder - that nado. Znachit, I have a 
good programmist. Dannaya statya have You tried it razveyat

deep zabluzhdenie. In the first place
ona adresovana those zanimaetsya sozdaniem games and those who 
do not daet rest thought: "A tam what's inside?" To ponimaniya 
dostatochno znaniya bases Beysika and his takih structures, 
two-HOW massivy. 

 Zadacha nahozhdeniya samogo short path
by some tochkami between A and B, nA playing field with 
arbitrary raspolozhennymi harakterna obstacles, especially for 
popular today takticheskih and strategicheskih games. HOW 
podzadacha, ona can voznikat prakticheski any igrah -

RPG, kvestah, logic (a typical example
- "Color Lines", kstati, blind the next version of takoy toys 
after stati - raz spit). Why nado iskat samy short marshrut? In 
some igrah, naprimer "UFO-2", "Laser Squad", the length of the

marshruta zavisit number potrachennyh
units of time - than will optimalney
nayden path, the soldier will get faster
to the target. A, naprimer in "Color Lines"
dlina marshruta not ogovorena pravilami,
znachenie has only sam fakt opportunities
or the inability to move shara.No in
this game will look nice if
sharik srazu napravitsya kuda nado, a not
will zagadochno defilirovat across the board.

 The solution to this zadachi came to Us from takoy dalekoy, 
kazalos would the games oblasti HOW elektronika. A is - 
razvodka pechatnyh plat (all znayut it takoe?).  There are many 
trassirovschikov (programm for razvodki platy) osnovannyh nA no 
fewer razlichnyh methods zanimayuschihsya compound kontaktov 
two single conductor. But we rassmotrim only one of them, samy

simple (a znachit, samy samy nadezhny and
popular) - Wave trassirovschik.

 Postavim before the wave trassirovschikom
zadachu in terminah razrabatyvaemoy nami
Games:
 There is a level playing field P (MxN), where M and N,
respectively razmer field of vertikali
and gorizontali. Simply, it is massiv razmernostyu MxN (DIM P 
(M, N)). Kazhdaya kletka playing field (element massiva) can 
obladat large number of properties on vashemu discretion, but 
only for nas vazhno one - its patency (or obstruction). Kakim 
obrazom ona determined - vashe that's the case. Dalshe: there 
nekotoraya startovaya tochka where nahoditsya hero vashey game 
and konechnaya tochka, kuda him must popast. Poka We agree that

He could walk only four napravleniyam (which requires nas 
klassichesky wave method) - vpravo, left, forward,

nazad. Want to move him from
CAREERS starta to finish za naimenshee number of moves, if at 
all possible takoe movement. 

 Algorithm nahozhdeniya kratchayshego marshruta
between the two tochkami for takoy zadachi dostatochno simple:

 1. Snachala need sozdat rabochy
massiv R (MxN), ravny on razmeru massivu
playing field P (MxN)
 2. Each time an element rabochego massiva
R (i, j) prisvaivaetsya some znachenie in
zavisimosti on the properties of elementa game
field P (i, j) the following pravilam:
 a) If the field P (i, j) 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
(Final) position, then R (i, j): = 0;
 d) If the field P (i, j) is startovoy
position, then R (i, j): = 253.
 3. Etap "Rasprostraneniya waves." Introduce
variable Ni - counter iteratsy (repetitions) and prisvaivaem 
her nachalnoe znachenie 0.  4. Introduce konstantu Nk, which 
ustanavlivaem ravnoy maksimalno possible number iteratsy.  5. 
Line prosmatrivaem rabochy massiv R (ie, large screen enclosed 
organizuem tsikla: Index massiva i from 1 to M, the massiva 
index j from 1 to N).  6. If R (i, j) raven Ni, then 
просмaтривaютсясоседниеэлементыR (i +1, j), R (i-1, j), R (i, j 
+1), R (i, j-1) following pravilu (as a possible primera 
rassmotrim R (i +1, j)):

 a) If the R (i +1, j) = 253, then go to
paragraph 10;
And b) If the R (i +1, j) = 254, holds prisvaivanie R (i +1, 
j): = Ni +1;  c) In all ostalnyh a case of R (i +1, j)

ostaetsya unchanged.
 Analogichnopostupaem with elementami
R (i-1, j), R (i, j +1), R (i, j-1).
 7. By zaversheniyu interline prosmotra
all massiva uvelichivaem Ni nA 1.
 8. If Ni> Nk, search marshruta priznaetsya neudachnym. Exiting 
programmy.  9. Go to step 5.

 10.Etap build marshruta movement. Prisvaivaem variables X and 
Y znacheniya koordinat startovoy position.  11.V vicinity of 
the position R (X, Y) are looking for element naimenshim 
znacheniem (ie This prosmatrivaem R (X +1, Y), R (X-1, Y),

R (X, Y +1), R (X, Y-1)). Koordinaty this
elementa zanosim the variables X1 and Y1.
 12.Sovershaem movement obekta (who
tam y vas to be - a robot akvanavt, Winnie the Pooh) on the 
playing field from the position [X, Y] in position [X1, Y1]. 
(By zhelaniyu, you can predvaritelno zanosit koordinaty X1, Y1

in some massiv, and only zakonchiv
construction of all marshruta, zanyatsya movement hero ekrane 
nA). , 13.Esli R (X1, Y1) = 0 then go to step 15.

 14.Vypolnyaem prisvaivanie X: = X1, Y: = Y1.
Go to step 11.
 15.Vse!

 For those who are srazu realized recommend
dalshe not chitat. For people normalnyh
I repeat still raz with PURPORT and explanations:

 1. Snachala need sozdat rabochy
massiv R (MxN), ravny on razmeru massivu
playing field P (MxN).

REM> Poka simple. Ha BASIC - just
komanda DIM R (M, N). assemblere Ha -
something tipa "_R DEFS _M * _N". If the playing field a lot, 
it makes sense to a window, kuda popadayut nachalnaya and

konechnaya point (naprimer in "UFO-2. Devils are deep" in the 
field razmere 64x64 rabota is only chastyu field 32x32) that  
would ogranichit number of calculations. 

 2. Each time an element rabochego massiva
R (i, j) prisvaivaetsya some znachenie in
zavisimosti on the properties of elementa game
field P (i, j) the following pravilam:
 a) If the field P (i, j) 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
(Final) position, then R (i, j): = 0;
 d) If the field P (i, j) is startovoy
position, then R (i, j): = 253.

REM> also without complications. Come on
massivu playing field F, define prohodima / neprohodima 
tekuschaya kletka, in accordance with this zapisyvaete in cell 
massiva R number 254/255. According to zavershenii the position 
of start / stop zanosite 253 / 0. There are several ways 
zadaniya properties elementa playing field. Primera specific 
large screen: the "NLO1 / 2" organizovan baytovy massiv 
properties spraytov landshafta, Each time a bat has its own 
property, za patency otvechaet, naprimer, the seventh bit. In 
"Black Crow" sdelano easier - sprayty with nomerami from 0 to 
31 - Passable, starshe - no.


 3. Etap "Rasprostraneniya waves." Introduce
variable Ni - counter iteratsy (repetitions) and prisvaivaem 
her nachalnoe znachenie 0. 

REM> Etap nazvan tak because zapolnenie rabochego massiva 
really napominaet wave. Obratite vnimanie that rasprostranenie 
wave nachinaetsya with the endpoint. 

 4. Introduce konstantu Nk, which ustanavlivaem ravnoy 
maksimalno possible number iteratsy. 

REM> It's a very delicate moment. Suppose that between nachalom 
and the end is insurmountable obstacle, togda search

zaydet way to a standstill and programma zatsiklitsya. To avoid 
this, and introduces a takaya peremennaya. Her velichina 
podbiraetsya eksperimentalno.Naprimer, in the same

"UFO-2" dazhe akvanavt-general, having 108
units of time and a lot of energy can not
za course will move more than nA to 27 cells. Odnako I still 
sdelal Nk = 64. In either a case of when nashem method of 
solving zadachi Nk can not prevyshat 253 (dogadalis why). 

 5. Line prosmatrivaem rabochy massiv R (ie, large screen 
enclosed organizuem tsikla: Index massiva i from 1 to M, the 

  massiva index j from 1 to N)

REM> Dumayu, of course, is HOW sdelat nA
BASIC. Ha assemblere I would not stal delat tsikla large 
screen, a sdelal least one, remembering that line in memory is 
massiva hranyatsya za each other and obrazuyut continuous chain 
baytov. 

 6. If R (i, j) raven Ni, then просмaтривaютсясоседниеэлементыR 
(i +1, j), R (i-1, j), R (i, j +1), R (i, j-1) following 
pravilu (as a possible primera rassmotrim R (i +1, j)):

 a) If R (i +1, j) = 253, then go to
paragraph 10;
 b) if R (i +1, j) = 254, holds prisvaivanie R (i +1, j): = Ni 
+1;  c) In all ostalnyh a case of R (i +1, j)

ostaetsya unchanged.
 Analogichnopostupaem with elementami
R (i-1, j), R (i, j +1), R (i, j-1).

REM> A few points to programmiruyuschih nA assemblere. Because 
we are looking sovpadenie massiva elements with only one number 
(Ni), in order to achieve naibolshey speed poiska recommended 
ispolzovat komandu CPIR. Second zamechanie: when fiksirovannyh 
razmerah playing field adresa adjacent elements can not compute 
for complex formulam, a zadat numeric offset (naprimer, at a 
field 32x32 displacement of the four neighboring cells ravny

-32, -1, +1, +32). Third zamechanie, vazhnoe for all: a lot of 
time in the calculations can account otnimat kraevyh effects 
(Meaning the elements raspolozhennye nA granitsah massiva). 
Indeed, if naprimer, i = 1, then to obraschenie R (i-1, j) has 
no smysla and may lead to perish dannyh and zavisaniyu 
kompyutera. I recommend further in paragraph 1 sozdat rabochy

massiv razmerom not nA M N, a (M +2) x (N +2)
and all dat granichnym elementam znachenie
255 (impassable). The memory is a little tratitsya
more zato programmirovat easier, and yes
raschety will go faster. Tak and I delal
in "UFO-2.

 7. By zaversheniyu interline prosmotra
all massiva uvelichivaem Ni nA 1.

 8. If Ni> Nk, search marshruta priznaetsya neudachnym. Exiting 
programmy. 

REM> I vas a little obmanul. Matematicheski exact conditions 
neudachnogo poiska zvuchat tak: "If nA current shage no naydeno 
no elementa R (i, j), ravnogo Ni, then marshruta connecting the 
two points that are not There. "You can vospolzovatsya

pravilom this if you like absolyutnuyu
Accuracy (in this a case of parametr Nk does not need one), but 
I kazhetsya better sdelat one test at the end than a hundred nA 
etape poiska.  Yes, I almost zabyl, Algorithm rasprostraneniya 
wave can prekrasno ispolzovatsya for zalivki small pieces of 
arbitrary shape. Tak, if you want sozdat its own Art Studio, 
and the head did not climb, can ispolzovat this method (for 
this vybrasyvaem items 10-15 and slegka modify Algorithm.

HOW? Pridumayte sami).

 9. Go to step 5.

REM> That is prodolzhaem generatsiyu wave.

 10.Etap build marshruta movement.
Prisvaivaem variables X and Y znacheniya koordinat startovoy 
position. 

 11.V vicinity of the position R (X, Y) are looking for
element naimenshim znacheniem (ie
This prosmatrivaem R (X +1, Y), R (X-1, Y),
R (X, Y +1), R (X, Y-1)). Koordinaty this
elementa zanosim the variables X1 and Y1.

REM> way to view the surrounding elements
analogichen what HOW is delalos in paragraph 6. If vash the 
hero is able to walk on diagonali, you can include in your 
searches, and more four neighboring diagonalnyh elementa,

nado view that in the first place. Tak same, but slightly more 
complicated in sdelano "UFO-2 (at rassmotrenii diagonalnyh

uchastkov navigate pravilam taken to bolshinstva strategy 
should not be hindering traffic or sprava sleva).


  Vnimanie! Takoy way ucheta diagonalnyh movements daet 
approximately 95% probability nahozhdeniya really samogo short 
marshruta. Ha my opinion, this quite dostatochno. If unto you 
suddenly need a samy a short way from garantiey nA to 100%, 
already in paragraph 6, you must prinimat in vnimanie 
diagonalnye elements based nalozhennyh vashey ogranicheny game. 
Speed ​​rasprostraneniya wave thus strongly padaet.


 12.Sovershaem movement obekta the game field from the position 
[X, Y] in the position [X1, Y1]. (By zhelaniyu, you can 
predvaritelno zanosit koordinaty X1, Y1 in a massiv, and only 
building the whole zakonchiv marshruta, zanyatsya movement Hero 
ekrane nA). 

REM> Zanosit koordinaty marshruta in takoy intermediate list 
makes sense, if both vas peremeschaetsya several characters, a 
memory is only vydelena under one rabochy massiv R. Or, if

place in the R stands out in a certain general oblasti that 
others may podprogrammy ispolzovat fit your needs. Kstati can 
not zapominat sami koordinaty, nA that in nashem allow 2 bayta 
example, a code napravleny movement nA dostatochno and that one.


 13.Esli R (X1, Y1) = 0 then go to step 15.
REM> Well, we got to handle, ie to
onechnoy point.

 14.Vypolnyaem prisvaivanie X: = X1, Y: = Y1.
Go to step 11.

 15. Everything!

Pravda is not just? In izbezhanii ambiguities in this issue is 
zhurnala nA simple example of BASIC. Looking

it, you HOW least be able to repeat
"Color Lines".

Dostoinstva and nedostatki metoda.

 Dostoinstva - prostota, nadezhnost, 100%
samy shortest path (for klassicheskogo
metoda). Nedostatki - a large amount of memory is required and 
no samaya vysokaya rate nahozhdeniya way. In "UFO-2, when the 
conditions listed above, the path may nahozhdenie dostigat time 
to 1 / 10 seconds. This, of course, acceptable to poshagovyh

strategy and logic toys, but hardly suitable for dinamicheskih 
games. A pro attempt realizatsii nA BASIC I do

silence (razve as a possible primera).

 Variatsii metoda.

 Dvoynaya volna - rasprostranenie wave
HOW nachinaetsya from the end, and from tak nachalnoy point, a 
marshrut prevalent made from two uchastkov - from the point of 
meeting waves to starta until finisha. Theoretically, can

increase the speed poiska 3-4 raza.No
Here's HOW nA praktike?

 In a case of acute nehvatki memory is, naprimer if you do not 
zadumali game, a samy nastoyaschy trassirovschik plat nA 
Spectrum, can be used truncated kodirovanie

wave. Ie pervaya volna is number 1,
vtoraya - 2, the third - snova 2, chetvertaya
-1, And tak dalee. Ha encoding one elementa require large 
screen bita (chisla 0 / 3 will be traversed opisyvat / 
impassable field).  When searching for search marshruta 
adjacent cells The memory in the same order (... 1 1 2 2 1 1

2 2 1 1 2 2 ...). None of kakih diagonalnyh
movements can not be considered.

 In addition to the wave, there sravnitelno
large number of methods for poiska
marshrutov. Somewhere required naibolshaya
raschetov speed at the expense of kachestvu,
somewhere - naimenshee number of rotations,
somewhere - need to marshrut obyazatelno went through some of 
the key point (nevazhno in kakom order). New

Methods trassirovki allow iskat marshruty where the path may be 
held under any uglami (not just kratnymi 90-a and

45 and gradusam). Progress does not stand nA place.

 Therefore zakonchit statyu want slovami
VI Lenina, skazannymi them nA III Congress
Young Communist League: "Learn, learn and learn - that
vasha glavnaya zadacha!

P.S. I would like to poblagodarit prepodavateley SPbGTU (ETU) 
with kafedry SAPR, which I have all this nauchili, a I, HOW 
could rasskazal unto you. Well, even raz napominayu who want to 
stat nastoyaschim programmistom should go only to the 
institution directly nA kafedru this:) 

Vsegda vash, Vyacheslav Mednonogov.
_______________________________