OpenEuphoria

Re: lots o stuff

• Posted by Hawke <mdeland at NWINFO.NET> Oct 16, 1998
• 702 views

noah smith wrote:
>Ok, here's what I have:square, tile-based system,
>with an "army" at location (x,y).
<snip>
>i am trying to write an optimized algorithm which
>which determines all legal movement for an army in one turn

take a look at the following 'code fragment' and see
what you think, and if it's faster than your method...
it's not really tested, but the logic is what you're
after anyway...

take care--Hawke'

----------------begin fragment
constant maxDIR=8,         --max number of directions
         maxPEN=4,         --highest terrain penalty (0..4)
         maxTYPES=3,       --number of 'types'
         maxTER=5,         --number of terrain types
         maxOBJ=100,       --number of object types
         maxMOB=100,       --number of mob types
         minMAP={1,1},     --min coordinates for the map
         maxMAP={100,100}, --max coordinates for the map
         maxRANGE=6        --farthest any mob/plr can move
         XI=2,YI=1,        --X index and Y index
         TI=1,DI=2,        --TYPE index and DATA index
         NORTH=1,NE=2,EAST=3,SE=4,
         SOUTH=5,SW=6,WEST=7,NW=8,
         --this is a list of offsets that apply to a coordinate
         --pair for a given direction
         DIRLIST={ {0,-1},{1,-1},{1, 0},{ 1, 1},
                   {0, 1},{-1,1},{-1,0},{-1,-1} },
         TERRAIN=1,OBJECT=2,MOB=3
sequence map
--map is a 2d seq, lineXcol ordered, which holds the 'world'.
--At each intersection there is a pair of values {TYPE,DATA}
--where TYPE is what is being held there (mob,terrain, or object)
--and DATA is the data related to what is held there. If TYPE is
--mob, then DATA would be its mob number, if it's terrain then
--DATA would be what kind of terrain, etc.
sequence moblist,objlist,terlist
object   junk,temp

--build map
--let's create some random world information...
map = repeat ({{},{}},maxMAP[XI]) --a line of Xcoord's
map = repeat (map,maxMAP[YI])     --a 'list' of lines
for i=1 to maxMAP[YI] do
   temp=repeat({{},{}},maxMAP[XI])
   for j=1 to maxMAP[XI] do
        junk=rand(maxTYPES)
        if    junk=TERRAIN then
                temp[j]={junk,rand(maxTER)}
        elsif junk=OBJECT
                temp[j]={junk,rand(maxOBJ)}
        else    temp[j]={junk,rand(maxMOB)}
        end if
   end for
   map[i]=temp
end for

--build terlist
--terlist holds the penalties for each 'type' of terrain
terlist=repeat(0,maxTER)
for i=1 to maxTER do
   terlist[i]=rand(maxPEN) --fill it with penalties of your choosing
end for

--build moblist
moblist={} --whatever you want

--build objlist
objlist={} --whatever you want


function Max(object a,object b)
   return a*(a>=b) + b*(b>a)
end function

function Min(object a,object b)
   return a*(a<=b) + b*(b<a)
end function

function FixBoundary(sequence point)
--determines if a point is on the map, and adjusts
--bad coordinates into good coordinates
   point = Max( point,minMAP ) --careful here...
   point = Min( point,maxMAP )
   return point
end function

function CheckDIR(sequence map, sequence center,
                  atom direction, atom range)
--Given a direction to travel, from a central point 'center',
--determine the last possible point that can be visited.
--This point will be within the distance 'range' along that
--direction, and will stop just before an obstruction is reached.
--Obstructions are defined as anything that *is not* terrain.
--Fractional penalties are accounted for.  If a border is reached,
--it will keep moving parallel to that border if the direction
--is diagonal, or it will simply stop at the border if the
--direction is along the X or Y axis.
sequence testpoint, goodpoint, terrain, offset, temp
atom penalty
atom testX, testY
   goodpoint= center
   testpoint= center
   offset   = DIRLIST[direction]
   while range >= 0 do
       testpoint= FixBoundary(testpoint + offset)
       testX    = testpoint[XI]
       testY    = testpoint[YI]
       --what's at this point on the map?
       temp     = map[testY][testX]
       --remember, TI is TYPEindex, and DI is DATAindex
       if temp[TI] != TERRAIN then --must be obj or mob
          return goodpoint
       end if
       terrain  = temp[DI]         --pick up the terrain type
       penalty  = terlist[terrain] --look up it's penalty
       range    = range - penalty
       goodpoint=testpoint --update the last known 'valid' location
   end while
   return goodpoint
end function

function FindValidMoves(sequence map, sequence center, atom range)
--Build a list of all locations that can be visited,
--in all directions, from the starting point 'center', for
--a distance around that point of 'range'.
sequence movelist movelist={}
   for direction=1 to maxDIR do
      movelist=movelist & CheckDIR(map,center,direction,range)
   end for
   return movelist
end function

? junk

--hope that worked...