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.
_______________________________
