Differences between revisions 13 and 14
 ⇤ ← Revision 13 as of 2007-04-30 21:05:04 → Size: 3575 Editor: TracyHarms Comment: ← Revision 14 as of 2008-12-08 10:45:53 → ⇥ Size: 3577 Editor: anonymous Comment: converted to 1.6 markup Deletions are marked like this. Additions are marked like this. Line 112: Line 112: *On this topic, see the note by Edsger W. Dijkstra, [http://www.cs.utexas.edu/users/EWD/transcriptions/EWD08xx/EWD831.html Why numbering should start at zero.] [[BR]] *On this topic, see the note by Edsger W. Dijkstra, [[http://www.cs.utexas.edu/users/EWD/transcriptions/EWD08xx/EWD831.html|Why numbering should start at zero.]] <
>

Requirement: Support movement on a square game-board on which movement is allowed off each edge as though the opposite edge were adjacent. A move is always a unit move, as with the king in chess. A four-by-four map and example moves are shown here.

```   i. 4 4       NB. show the map on which movement occurs
0  1  2  3
4  5  6  7
8  9 10 11
12 13 14 15

E move 5     NB. move east from location 5
6
SE move 11   NB. move south-east from location 11
12
SW move 12
3
NW move W move NW move 1
10```

A natural way to solve this is by working with arrays that model the mapping.

```NB. Movement on square map with toroidal wrap.
NB. (model-based algorithm)

sz =: 4            NB. size (edge-length) of square map
loc=: i. sz, sz    NB. model of mapped locations
'NW N NE W E SW S SE' =: compass=: c#~ +./"1 |c=. <: 3&#.^:_1 i.9

t=. verb : '(<:sz)}. (1+2*sz)\$ loc {~ y|~ #loc'
tloc=: (<:sz)}."2 t"0 i.1+2*sz        NB. transit model

tloc {~<,x + 1 1 + ,4 \$. \$. loc = y
)
NB. x is direction of movement
NB. y is location before move
NB. output is location after move
NB. i.sz^2 is domain of both output and y-input ```

The solution can also be obtained without creating arrays that are analogous to map positions.

```NB. Movement on square map with toroidal wrap.
NB. (formulaic algorithm)

sz =: 4       NB. size (edge-length) of square map
'NW N NE W E SW S SE'=: compass=: c#~ +./"1 |c=. <: 3&#.^:_1 i.9

xx =. }.x
if.     0>xx do. xx+  sz *    0  = sz|y    NB. West
elseif. 0<xx do. xx+(-sz)* (sz-1)= sz|y    NB. East
elseif.      do. 0
end.
)

xx =. }:x
s2 =. sz^2
if.     0>xx do. (-sz)+s2* y < sz          NB. North
elseif. 0<xx do. sz   -s2* y >:s2-sz       NB. South
elseif.      do. 0
end.
)

y + +/ (x deltaNS y),(x deltaEW y)
)```

In the game-design classroom context where this problem arose, the locations on the four-by-four map were to be numbered from one to sixteen, and the eight possible directions of movement were to be received as particular codes. Arbitrary input-output format requirements such as this can be handled easily.

```moveA=: dyad define    NB. use alternate I/O domains
1+ (y-1) move~ ,compass#~ x= _5 _4 _3 _1  1  3  4  5
)

_3 moveA 12   NB. _3 means NE, as diagrammed below
5

NB. directions of movement as (non-wrapping) differential on 4-by-4 array
] 3 3 \$ _5 _4 _3 _1 0 1  3  4  5
_5 _4 _3
_1  0  1
3  4  5

>: i. 4 4   NB. 1-based array
1  2  3  4
5  6  7  8
9 10 11 12
13 14 15 16```

The difference between zero-based numbering and one-based numbering is of no consequence here.* The classroom specification for signaling direction of movement, however, is unfortunate. It binds the concept of direction to the size of the map. Change to a map of size other than 4x4 would invalidate what little meaning these numbers have, and any code that relied on those values in anything but a token manner would require rewriting. In the code shown here, these values are used as mere tokens. The elements of compass are not tokens; they denote direction of change, north-south and east-west.

```   compass   NB.  NW N NE W E SW S SE
_1 _1
_1  0
_1  1
0 _1
0  1
1 _1
1  0
1  1```

*On this topic, see the note by Edsger W. Dijkstra, Why numbering should start at zero.

TracyHarms/misc/wrapmap (last edited 2008-12-08 10:45:53 by anonymous)