Eric: The Mysterious Stranger - RTS game(WIP)

[leopardpm]

Yes. The issue is pathfinding around moving agents. I don't want to have to re-calculate paths for every agent every time another agent moves onto their path.

pathfind normally, but ignoring all other agents... and with each step check to see if the tile is clear... if not then:

1: you can either re-pathfind at that time, or

2: check to see if whatever agent which is in the way is currently moving, and then do one of two things:
a: If moving, then waiting until that agent has moved on and out of the way
b: if not moving, then re-pathfind but this time mark the path blocked where the blocking agent is

I'm working under linux now so I'm still trying to get my game compiling before I can do any more work on it.

sounds like a pain!

[BasicCoder2]

pathfind normally, but ignoring all other agents... and with each step check to see if the tile is clear... if not then:

Which tile? The sprite can straddle 2 to 4 tiles when it collides with another sprite. Moving sprites pixel to pixel (or less) in a tile world creates issues not found when they just jump tile to tile.
.

[Boromir]

pathfind normally, but ignoring all other agents... and with each step check to see if the tile is clear... if not then:

Which tile? The sprite can straddle 2 to 4 tiles when it collides with another sprite. Moving sprites pixel to pixel (or less) in a tile world creates issues not found when they just jump tile to tile.
.

Yes, another issue is when an agent moves in front of another agent who has already calculated his path. I'm thinking I will just make agents slide around each other. With many agents in an area it could get congested but I'm willing to deal with that in order to cut performance costs.

[BasicCoder2]

Boromir wrote: I'm thinking I will just make agents slide around each other.

Kind of vague what that "slide around each other" might mean?

I would have thought that what to do when two agents meet while on a path to some goal target would be fundamental. They may want to chat or exchange goods or fight it out. It seems to me that you need to turn off the path following and push the "move to target" goal onto a stack while the collision is dealt with.

Imagine the scenario of people walking along a pavement and having to avoid colliding with those walking the other way.

At this point in time your code allows two or more agents to occupy the same positions which looks kind of strange.

Another question is: Does the path generator take into account the current position of other agents, keeping in mind they may not be moving and are essentially obstacles. This is made harder because the path positions are in tile resolutions whereas the agent's positions are in pixel resolutions.

The sprite collision detector I use uses rectangle overlap detection and that is at the pixel level. These means the agents may be somewhere between tiles at the collision event.

.

[leopardpm]

BasicCoder2: Which tile? The sprite can straddle 2 to 4 tiles when it collides with another sprite. Moving sprites pixel to pixel (or less) in a tile world creates issues not found when they just jump tile to tile.
Always only collide on the tile where feet are... the pixels of the head will 'collide' but should not interfere with whatever tile the 'head' is actually in because it isn't there, it is in front of...

BasicCoder2: The sprite collision detector I use uses rectangle overlap detection and that is at the pixel level. These means the agents may be somewhere between tiles at the collision event.
colliding on a per pixel level will be a problem because the agents are not 'really' per pixel, they are tile based and the per pixel movement is specific to any two adjacent tiles, not any two tiles in general.... so if you collide while 'in between' then your easy choice for response is to go back to the tile the agent 'came from' - this will not look good. Best NOT to collide based on per pixel, but instead to do it based on each agents associated tile (closest tile).
Boromir: Yes, another issue is when an agent moves in front of another agent who has already calculated his path. I'm thinking I will just make agents slide around each other. With many agents in an area it could get congested but I'm willing to deal with that in order to cut performance costs.
every agent will always be associated with a certain tile even if moving per pixel. Basically, if the agent is in between tiles (moving per pixel), have it associate with the closest one... the first half of his per pixel movement will be considered in the original tile, and the 2nd half of his per pixel movement will be associated with the destination tile... for collision purposes. The line in RED is wrong, now thinking about it... always have the agent associated tile be the one he is moving towards, not the one he came from else will have collisions partway which gives rise to the issue above that I discussed.

Making them 'slide around' each other could introduce other issues which we cannot foretell at this point, best to just re-calculate the path. This avoids issues.

From what I can tell, your paths will all be under 50 tiles long, probably a lot shorter... so calculating these and re-calculating them when there is a collision will not be a performance hit. At this point, don't worry about performance of the pathfinding/collision, that can be dealt with as needed later on - first get things working correctly, behaving and looking right, THEN we can see if there are any performance issues (which I seriously doubt there will be...)

[BasicCoder2]

BasicCoder2: Which tile? The sprite can straddle 2 to 4 tiles when it collides with another sprite. Moving sprites pixel to pixel (or less) in a tile world creates issues not found when they just jump tile to tile.
Always only collide on the tile where feet are... the pixels of the head will 'collide' but should not interfere with whatever tile the 'head' is actually in because it isn't there, it is in front of...

Without code it is difficult to know what you are talking about. There is a collision rectangle of some width and height regardless of the actual image size and it can overlap up to four tiles. Rather than clog up this thread on the subject perhaps look at some old code I have just posted to the GameDev section.
.

[Boromir]

Always only collide on the tile where feet are... the pixels of the head will 'collide' but should not interfere with whatever tile the 'head' is actually in because it isn't there, it is in front of...

Lets talk in the terms of a top down 2d game because that is how mine works underneath the graphics layer. Each agent is a square that can take up space on up to 4 map tiles. I'm going to do collision on the agent's square not the map tiles for better looking results.

every agent will always be associated with a certain tile even if moving per pixel. Basically, if the agent is in between tiles (moving per pixel), have it associate with the closest one... the first half of his per pixel movement will be considered in the original tile, and the 2nd half of his per pixel movement will be associated with the destination tile... for collision purposes. The line in RED is wrong, now thinking about it... always have the agent associated tile be the one he is moving towards, not the one he came from else will have collisions partway which gives rise to the issue above that I discussed.

It's not hard to pathfind around an estimated agent map tile position but since an agent can be in up to 3 other tiles agents will still walk through each other. Bocking all 4 is an option that I don't like but that might work sufficiently for maps without many agents.

[leopardpm]

ok, so a unit can occupy up to 4 tiles with their 'feet', then definitely block out all four tiles for pathfinding, why don't you like this option? It doesn't take any longer to pathfind and hardly any time to block out 4 tiles per agent before pathfinding...

I'm going to do collision on the agent's square not the map tiles for better looking results.

actually, unless you have some pretty complex code for the collision response, doing the collision test on per pixel could look worse... by focusing on just tile collision the code is simpler and the worst case is that there is a slight distance between agents (of up to 1 tile distance) when they decide to take another path around... not a bad thing, could even end up making them look a bit smarter as they are 'looking ahead' a bit and not waiting until actual collision before choosing to avoid...

[BasicCoder2]

This is one way I tried to overcome the problem:
In this example each sprite in turn finds a direction (as defined by the xd and yd increments) which will lead to a clear tile. It assigns that tile as filled to prevent the next sprite choosing it as well. They then start moving by adding the xd and yd increments. (They must be increments of one pixel in this example because of how the position of the next tile is calculated). They keep moving until they are on the next tile. When all sprites are on the their next tile they can clear that tile and then check to see if the next tile is clear so they can keep moving in the same direction. If the next tile in the current direction is filled they choose another set of increments that will lead to a clear tile.

So the sprites never change direction until they are all on a tile. They move pixel by pixel between tiles. Essentially it is the same as having the collision logic of sprites that jump from tile to tile. A collision means the next tile is filled with something. It could be another sprite.

The border tiles were filled to avoid having to check for out of boundary conditions.

Code: Select all

screenres 640,480,32
color rgb(0,0,0),rgb(255,255,255):cls
dim shared as integer world(20,15)
for j as integer = 0 to 14
    for i as integer = 0 to 19
        read world(i,j)
    next i
next j

dim shared as any ptr tinyWalker
tinyWalker = imagecreate(256,256,rgb(255,0,255))
'bload "tinyWalker.bmp",tinyWalker
'fill with green frames
for j as integer = 0 to 7
    for i as integer = 0 to 7
        line tinyWalker,(i*32,j*32)-(i*32+31,j*32+31),rgb(0,255,0),b
    next i
next j


type AGENT
    as integer x
    as integer y
    as integer w
    as integer h
    as integer xd
    as integer yd
    as integer d   'direction flag
    as integer f   'current animation frame
    as any ptr img  'image block
end type

dim shared as AGENT ag(0 to 4)

'initialize agents
for i as integer = 0 to 4
    ag(i).x = i*64+128
    ag(i).y = 5*32

    ag(i).w = 32
    ag(i).h = 32
    ag(i).xd = int(rnd(1)*3)-1
    ag(i).yd = int(rnd(1)*3)-1
    while ag(i).xd = 0 and ag(i).yd=0
        ag(i).xd = int(rnd(1)*3)-1
        ag(i).yd = int(rnd(1)*3)-1
    wend
    world(ag(i).x\32+ag(i).xd,ag(i).y\32+ag(i).yd) = 1 'set destination tile as taken
    ag(i).x = ag(i).x + ag(i).xd  'make first move off this tile
    ag(i).y = ag(i).y + ag(i).yd  'so as not to set on onTile flag
    ag(i).img = tinyWalker
next i

sub drawWorld()
    screenlock
    cls
    'draw world
    for j as integer = 0 to 14
        for i as integer = 0 to 19
            if world(i,j)=0 then
                line (i*32,j*32)-(i*32+32,j*32+32),rgb(0,0,0),b
            else
                line (i*32,j*32)-(i*32+32,j*32+32),rgb(100,100,255),bf
            end if
        next i
    next j
    'draw sprites
    for i as integer = 0 to 4
        line (ag(i).x,ag(i).y)-(ag(i).x+ag(i).w,ag(i).y+ag(i).h),rgb(0,255,0),b
    next i
    for i as integer = 0 to 4
        if ag(i).xd = 0 and ag(i).yd = 0 then ag(i).f = 1
        draw string (ag(i).x,ag(i).y),str(i)
        put (ag(i).x,ag(i).y), ag(i).img, (ag(i).f*32,ag(i).d*32) - (ag(i).f*32+31,ag(i).d*32+31),trans
    next i
    
    screenunlock
end sub

sub upDateFrame(ag as AGENT)
    If ag.xd =  0 and ag.yd =  0 then
        ag.f = 0  'not moving
    else
        ag.f = ag.f + 1
        if ag.f = 7 then ag.f = 0
    end if
end sub

function onTile(ag as AGENT) as boolean
    if ag.x = int(ag.x\32)*32 and ag.y = int(ag.y\32)*32 then
        return TRUE
    else
        return FALSE
    end if
end function
        
drawWorld()

'move agents off chosen tile
for i as integer = 0 to 4
    ag(i).x = ag(i).x + ag(i).xd
    ag(i).y = ag(i).y + ag(i).yd 
next i

sub moveAgents()
    dim as integer flag
    
    flag = 0  'flags ALL agent on center of their next selected tile
    
    for i as integer = 0 to 4
        if onTile(ag(i))=FALSE then 'keep moving
            ag(i).x = ag(i).x + ag(i).xd
            ag(i).y = ag(i).y + ag(i).yd
            flag = 1
        end if
    next  i
    
    if flag = 0 then  'all on center of next tile so we can check if next tile is free
        for i as integer = 0 to 4
            
            if world(ag(i).x\32+ag(i).xd,ag(i).y\32+ag(i).yd)=0 then 'next tile clear?
                
                world(ag(i).x\32,ag(i).y\32)=0  'clear current tile
                world(ag(i).x\32+ag(i).xd,ag(i).y\32+ag(i).yd)=1  'set next tile
                
            else
                
                do  'find another direction to move and if it is to a clear tile
                    ag(i).xd = int(rnd(1)*3)-1
                    ag(i).yd = int(rnd(1)*3)-1
                    while ag(i).xd = 0 and ag(i).yd=0
                        ag(i).xd = int(rnd(1)*3)-1
                        ag(i).yd = int(rnd(1)*3)-1
                    wend 
                loop until world(ag(i).x\32+ag(i).xd,ag(i).y\32+ag(i).yd)=0  'loop until found clear next tile
                
                world(ag(i).x\32,ag(i).y\32)=0  'clear current tile
                world(ag(i).x\32+ag(i).xd,ag(i).y\32+ag(i).yd) = 1 'set destination tile
                
            end if
            
            ag(i).x = ag(i).x + ag(i).xd  'make first move off tile
            ag(i).y = ag(i).y + ag(i).yd  'so not to trigger onTile next loop
            
        next i
    end if
    
end sub

dim as integer count

drawWorld()

do

    moveAgents()
    
    drawWorld()
    count = count + 1
    if count > 4 then
        count = 0
        for i as integer = 0 to 4
            upDateFrame(ag(i))
        next i
    end if
    
    
    sleep 20
    
loop until multikey(&H01)


sleep

data 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
data 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1

[Boromir]

After thinking about this some more I'm considering just marking all 4 tiles that an agent has a decent amount of foot on as obstacles for the pathfinder.

[leopardpm]

Yup, BC2, that is exactly what I was saying/suggesting

After thinking about this some more I'm considering just marking all 4 tiles that an agent has a decent amount of foot on as obstacles for the pathfinder.

yes, it is the proper way I think

[BasicCoder2]

After thinking about this some more I'm considering just marking all 4 tiles that an agent has a decent amount of foot on as obstacles for the pathfinder.

No you don't need to do that!!

Why I waffled on about the four tiles I don't know for sprite to sprite collisions only involve two rectangles and have nothing to do with sprite to tile issues.

When two sprites are moving toward each other you need a give way rule to say which one "steps aside" to let the other pass. In an open space maybe it is the one travelling left or up that must step aside. If there are obstacles the rule may be more complicated as a sprite cannot step aside onto an obstacle or another sprite.

When two sprites are going to cross each others paths with a collision then maybe the same rule as to who must give way but in this case giving way means pausing to allow the other to pass first.

Another issue I found in my experiments was that when two sprites pass by diagonally their rectangles will clip each other giving a false collision. The solution is for sprite to sprite collisions to be based on the distance between circles. That will also tell a sprite how close it is to another sprite even if not touching. Sprite to tile collisions can still use the overlapping rectangle test.
.

[Boromir]

After thinking about this some more I'm considering just marking all 4 tiles that an agent has a decent amount of foot on as obstacles for the pathfinder.

No you don't need to do that!!

Why I waffled on about the four tiles I don't know for sprite to sprite collisions only involve two rectangles and have nothing to do with sprite to tile issues.

We aren't talking about agent to agent collision. That's simple and easy. I thought we were discussing pathfinding around obstacles not on the grid.

When two sprites are moving toward each other you need a give way rule to say which one "steps aside" to let the other pass. In an open space maybe it is the one travelling left or up that must step aside. If there are obstacles the rule may be more complicated as a sprite cannot step aside onto an obstacle or another sprite.

When two sprites are going to cross each others paths with a collision then maybe the same rule as to who must give way but in this case giving way means pausing to allow the other to pass first.

That is essentially what I meant when I said "make agents slide around each other". I've made versions of these systems before. They work but when working with too many agents come out badly. Another problem is when an enemy warrior is blocking a passage. The pathfinding algo will tell him he can make it through. When he attempts it he will be stuck fighting with an enemy he didn't plan to face.

[leopardpm]

Why I waffled on about the four tiles I don't know for sprite to sprite collisions only involve two rectangles and have nothing to do with sprite to tile issues.

yes, they do matter. The pathfinding is tile-based and tiles (internally) can only have one unit in them at a time. As far as the iso display, the sprites will/can overlap (not their feet, but the head of a unit 'in front of' the feet of a unit 'behind'). Doing some sort of basic rectangle collision test (basically a sloppy per pixel collision UNLESS the rectangles cover only the feet) where the rectangles are not tile-aligned will give false collisions as well as instances where an agent is halfway between two tiles and collides which causes him to re-path 'somehow' but he is not on a tile directly which makes his pathing messy.

When two sprites are moving toward each other you need a give way rule to say which one "steps aside" to let the other pass. In an open space maybe it is the one travelling left or up that must step aside. If there are obstacles the rule may be more complicated as a sprite cannot step aside onto an obstacle or another sprite.

When two sprites are going to cross each others paths with a collision then maybe the same rule as to who must give way but in this case giving way means pausing to allow the other to pass first.

sure, this rule is fine... but still needs to be tile-based for pathing purposes

Another issue I found in my experiments was that when two sprites pass by diagonally their rectangles will clip each other giving a false collision. The solution is for sprite to sprite collisions to be based on the distance between circles. That will also tell a sprite how close it is to another sprite even if not touching. Sprite to tile collisions can still use the overlapping rectangle test.
.

this circumstance is totally avoided when using tile-based collisions - there is no problem with sprites overlapping (which they do naturally without actually colliding) when one is in front of the other or passing diagonally. No need for some sort of distance test, nor an arbitrary rectangle test which isn't tile-based.

[BasicCoder2]

My comments are based on actual code shown below. When following a path agents do not need to worry about unwalkable tiles they only need worry about collisions with other sprites. In the code below the agents are given random target tiles to walk to and a path to those tiles. They move tile to tile until they reach that target tile. When they reach the target another random target is chosen. When they collide with another sprite, as determined by rectangle overlap, the sprites involved are printed on the right during the collision. When you run the code you will perhaps see what I am talking about. You should see examples of sprites moving in opposite directions, sprites crossing over each other and sprites moving past each other diagonally.

Thinking about it now I guess if objects are added to a tile thus changing its walkable status after a path has been computed collisions with the newly added object could occur. In the code below I have not dealt with that possibility and what will happen is the sprite to tile collision will be caught and the ag.xd and ag.yd given a random value which is what I call the "wander mode" that I was using when a sprite was not following a path. In that case I would simply generate a new path to the target.

When a collision occurs the display will freeze so you can view the collision. Hold or tap the space bar until they begin moving again.

.

Code: Select all

type v2D
    as integer x
    as integer y
end type

const SCRW = 1280
const SCRH = 600

const TILEW = 16
const TILEH = 16
const TS = 16      'Tile Size same for width and height in this example

const MAPW = 40
const MAPH = 30


const CELL_UNUSED = 0
const CELL_OPEN   = 1
const CELL_CLOSED = 2

type NODE
    as V2D     current
    as V2D     parent
    as integer v
    as integer f      'score = g + h
    as integer g      'total from start to current
    as integer h      'total from current to end
    as integer state  'unused=0, open=1, closed=2
end type

dim shared as NODE world(MAPW,MAPH)

type APATH
    as v2D p(1000)  'need to make this variable
    as integer pCount   'length of path
end type

type AGENT
    as integer id        'id of agent
    as integer kind      'type of agent
    as integer x         'current position in pixels
    as integer y
    as integer w         'width of sprite
    as integer h         'height of sprite
    as integer xd        'velocity between -1 and +1
    as integer yd
    as ulong   c         'color of agent
    
    as integer item      'item held by agent
    as integer itemCount 'count items collected
    
    'required for astar routine
    as APATH    path      'path list
    as integer  counter   'position so far along path
    as integer  onThePath 'flag moving along path
    as v2D      target    'desired target
    
end type

dim shared as integer agentCount
agentCount = 8
dim shared as AGENT agents(0 to agentCount)

screenres SCRW, SCRH, 32
color rgb(0,0,0),rgb(255,255,255):cls
'------------------------------------------------------------------------------
'hold drawing which is then put onto screen
dim shared as any ptr DISPLAY
DISPLAY = imagecreate(MAPW*TILEW,MAPH*TILEH)

dim shared as integer WINW,WINH,WINX,WINY  'displayed area of bitmap
WINX = 0          'top/left corner of widow onto world array in pixels
WINY = 0
WINW = 40*TILEW   'width of array world
WINH = 30*TILEH
'========================================================================================
function testCollision(b1 as AGENT,b2 as AGENT) as boolean
    return b2.y < b1.y+b1.h and b2.y+b2.h > b1.y and b2.x < b1.x+b1.w and b2.x+b2.w > b1.x
end function
'=========================================================================================
sub clearCells()
    for y as integer = 0 to MAPH-1
        for x as integer = 0 to MAPW-1
            world(x,y).state = CELL_UNUSED
            world(x,y).g = 0
            world(x,y).h = 0
            world(x,y).f = 0
            world(x,y).parent.x = -1
            world(x,y).parent.y = -1
            world(x,y).current.x = x
            world(x,y).current.y = y
        next x
    next y
end sub


sub fillworld()
    clearCells()
    dim as integer r
    for y as integer = 3 to MAPH-1
        for x as integer = 0 to MAPW-1
            r = int(rnd(1)*5)
            if r = 0 then
                world(x,y).v = 1
            else
                world(x,y).v = 0
            end if
        next x
    next y
end sub

function makePath(sx as integer,sy as integer,ex as integer,ey as integer) as boolean
    
    clearCells() 'reset cells to compute new path
    
    dim as integer min,pass 'passable diagonal
    dim as integer ii,jj    'adjacent coordinate
    dim as integer x,y      'chosen coordinate
    dim as integer cx,cy    'current coordinates
    min = 0                 'minimum will be 9999 if all adjacent squares taken

    cx = sx
    cy = sy
   
    min = 9999   'will stay that value if no empty squares left
    
    while not(cx=ex and cy=ey) or min=9999
       
        world(cx,cy).state = CELL_CLOSED 'put on closed list ***********

        for j as integer = -1 to 1
            for i as integer = -1 to 1
               
                if i<>0 or j<>0 then  'avoid current position as adjacent position
                   
                    ii = cx+i  'coordinate of adjacent square
                    jj = cy+j
                   
                    'check boundary
                    if ii >= 0 and ii <MAPW and jj>=0 and jj<MAPH then
                       
                        'check if empty (walkable) and not closed
                        if world(ii,jj).v = 0 and world(ii,jj).state <> CELL_CLOSED then
                            
                            dim as integer newg
                            
                            'test if diagonal and passable
                            pass = 1 : newg = 10
                            if (i<>0 and j<>0) then 'diagonal move
                                if world(ii,cy).v <> 0 or world(cx,jj).v <> 0 then pass = 0 'not passable
                                newg =  14
                            end if
                            
                            
                            if pass = 1 then
                                newg += world(cx,cy).g
                                if world(ii,jj).state = CELL_UNUSED or world(ii,jj).g > newg then
                                    ' Manhattan with diagonals
                                    dim as integer xdiff, ydiff
                                    xdiff = abs(ii-ex) : ydiff = abs(jj-ey)
                                    if xdiff < ydiff then
                                        world(ii,jj).h = xdiff * 14 + (ydiff-xdiff) * 10
                                    else
                                        world(ii,jj).h = ydiff * 14 + (xdiff-ydiff) * 10
                                    end if
                                    
                                    world(ii,jj).g = newg
                                    world(ii,jj).parent.x = cx             'pointer to parent
                                    world(ii,jj).parent.y = cy
                                end if                                
                                
                                world(ii,jj).f = world(ii,jj).g + world(ii,jj).h

                                ' make it less preferrable to choose the non-straight line to goal
                                dim as integer dx1,dx2,dy1,dy2,cross
                                dx1 = cx - ex
                                dy1 = cy - ey
                                dx2 = ii - ex
                                dy2 = jj - ey
                                cross = abs(dx1*dy2 - dx2*dy1)
                                
                                world(ii,jj).f += cross
                                    
                                world(ii,jj).state = CELL_OPEN   'put on open list
                                
                            end if 'cell is passable
                        end if 'cell is walkable
                    end if 'boundary
                end if
            next i
        next j
       
        'find item on open list with lowest score
        min = 9999
        for j as integer = 0 to MAPH-1
            for i as integer = 0 to MAPW-1
                if world(i,j).state = CELL_OPEN then
                    if world(i,j).f < min then
                        x = i
                        y = j
                        min = world(i,j).f
                    end if
                end if
            next i
        next j
       

        if min = 9999 then  'no empties so no solution??
            return FALSE
        end if
       
       
        cx = x
        cy = y
       
    wend

    return TRUE
   
end function

function getPath(sx as integer,sy as integer,ex as integer, ey as integer) as APATH
    
    dim as APATH path
    dim as integer count
    dim as integer nx,ny
    dim as integer tx,ty
    
    makePath(ex,ey,sx,sy)

    tx = sx
    ty = sy
    
    Count = 0
    path.p(count).x = sx
    path.p(count).y = sy
    count = count + 1
    
    while world(tx,ty).parent.x <> -1
        
        nx = world(tx,ty).parent.x
        ny = world(tx,ty).parent.y
        
        path.p(count).x = nx
        path.p(count).y = ny
        count = count + 1 
        
        tx = nx
        ty = ny
    wend

    path.pCount = count
    
    return path
end function

sub drawWorld()
    dim as integer x,y,n
    screenlock
    cls
    line DISPLAY,(0,0)-(MAPW*TILEW-1,MAPH*TILEH-1),rgb(255,255,255),bf 'clear display
    
    for j as integer = 0 to  MAPH-1
        for i as integer = 0 to MAPW-1
            if world(i,j).v <>0 then
                line DISPLAY,(i*TILEW,j*TILEH)-(i*TILEW+TILEW,j*TILEH+TILEH),rgb(0,1000,200),bf
            end if
            line DISPLAY,(i*TILEW,j*TILEH)-(i*TILEW+TILEH,j*TILEW+TILEH),rgb(100,100,100),b
        next i
    next j
    line DISPLAY,(0,0)-(MAPW*TILEW-1,MAPH*TILEH-1),rgb(255,0,0),b
    
    'draw paths
    for i as integer = 0 to agentCount
        for k as integer = 0 to agents(i).path.pCount-2
            line DISPLAY,(agents(i).path.p(k).x*TILEW+7,agents(i).path.p(k).y*TILEH+7)_
            -(agents(i).path.p(k+1).x*TILEW+7,agents(i).path.p(k+1).y*TILEH+7),agents(i).c
            'circle DISPLAY,(agents(i).path.p(k).x*TILEW+7,agents(i).path.p(k).y*TILEH+7),3,rgb(0,0,0)
        next k
    next i
    
    for i as integer = 0 to agentCount
        'draw agent
        circle DISPLAY,(agents(i).x+8,agents(i).y+8),7,agents(i).c,,,,f
        line DISPLAY,(agents(i).x,agents(i).y)-(agents(i).x+TS-1,agents(i).y+TS-1),rgb(0,0,0),b
        'draw home base
        circle DISPLAY,(agents(i).target.x*TILEW+7,agents(i).target.y*TILEH+8),8,rgb(255,0,0),,,,f
        
        draw string DISPLAY,(agents(i).target.x*TILEW+6,agents(i).target.y*TILEH+6),str(i)
        draw string DISPLAY,(agents(i).x+6,agents(i).y+6),str(i)

        
    next i
    
    'test for sprite to sprite collision
    'and print collisions taking place
    dim as integer nxtLine,flag
    nxtLine = 0:flag = 0
    for j as integer = 0 to agentCount
        for i as integer = 0 to agentCount
            if i<>j then
                if testCollision(agents(i),agents(j)) then
                    draw string (700,nxtLine*16), "agent " & str(i) & " collided with agent " & str(j)
                    nxtLine = nxtLine + 1
                    flag = 1
                end if
            end if
        next i
    next j

    
    put (0,0),DISPLAY,(WINX,WINY)-(WINX+WINW-1,WINY+WINH-1),trans
    
    screenunlock
    
    if flag = 1 then sleep
    
end sub


sub followPath(ag as AGENT)

    if ag.counter < ag.path.pCount then
        ag.xd = ag.path.p(ag.counter).x - (ag.x\TILEW)    'get direction to move
        ag.yd = ag.path.p(ag.counter).y - (ag.y\TILEH)
        ag.counter = ag.counter + 1        'bump counter
    else
        ag.onThePath = 0
        ag.item = 0                        'drop item
        ag.itemCount = ag.itemCount + 1    'count items dropped
        ag.xd = 0
        ag.yd = 0
    end if
    
end sub

sub moveAgents(ag as AGENT)
    
    dim as integer hit
    dim as integer TILEX,TILEY
        
    hit = 0
    ag.x = ag.x + ag.xd
    ag.y = ag.y + ag.yd
        
    'out of bounds
    if ag.x\TILEW < 0 or ag.x\TILEH > MAPW-1 or ag.y\TILEW < 0 or ag.y\TILEH > MAPH-1 then hit = 1

    'test overlap of sprite with tile
    TILEX = int(ag.x/16)
    TILEY = int(ag.y/16)
    if world(TILEX,TILEY).v <> 0 then hit = 1

    TILEX = int((ag.x+15)/16)
    TILEY = int((ag.y)/16)
    if world(TILEX,TILEY).v <> 0 then hit = 1

    TILEX = int((ag.x)/16)
    TILEY = int((ag.y+15)/16)
    if world(TILEX,TILEY).v <> 0 then hit = 1

    TILEX = int((ag.x+15)/16)
    TILEY = int((ag.y+15)/16)
    if world(TILEX,TILEY).v <> 0 then hit = 1

    if hit = 1 then
        ag.x = ag.x - ag.xd 'undo move
        ag.y = ag.y - ag.yd 
        'new trial
        ag.xd = int(rnd(1)*3)-1
        ag.yd = int(rnd(1)*3)-1
        while ag.xd = 0 and ag.yd = 0
            ag.xd = int(rnd(1)*3)-1
            ag.yd = int(rnd(1)*3)-1  
        wend
    end if
        
end sub


sub update()
    
    dim as integer onTile
    
    for i as integer = 0 to agentCount
        
        onTile = 0
        
        if agents(i).x = int(agents(i).x\TILEW)*TILEW and agents(i).y = int(agents(i).y\TILEH)*TILEH then
            onTile = 1
        end if
        
        if onTile = 1 then
            if agents(i).onThePath = 1 then
                followPath(agents(i))  'reset increments to move to next tile
            end if
        end if

        if onTile = 1 and agents(i).onThePath = 0 then  'select a new target
            agents(i).target.x = int(rnd(1)*MAPW)
            agents(i).target.y = int(rnd(1)*MAPH)
            agents(i).path = getPath((agents(i).x\16),(agents(i).y\16),agents(i).target.x,agents(i).target.y)
            agents(i).onThePath = 1
            agents(i).counter = 0    'zero agent current index position on path    
        end if
        
        moveAgents(agents(i))

        
    next i


    drawWorld()
    
end sub


fillworld()  'fill world before setting paths

'================  INITIALIZE AGENTS =====================
for i as integer = 0 to agentCount
    agents(i).id = i
    agents(i).x = i*64
    agents(i).y = 32
    agents(i).w = TILEW
    agents(i).h = TILEH
    agents(i).c = rgb(int(rnd(1)*256),int(rnd(1)*256),int(rnd(1)*256))
    agents(i).target.x = int(rnd(1)*MAPW)
    agents(i).target.y = int(rnd(1)*MAPH)
    
    'set up first paths
    agents(i).path = getPath((agents(i).x\16),(agents(i).y\16),agents(i).target.x,agents(i).target.y)
    agents(i).onThePath = 1
    agents(i).counter = 0    'zero agent current index position on path   
    followPath(agents(i))    'set increments to move to next tile

next i
'===========================================================


drawworld()

dim as double now1
now1 = timer

do

    if timer > now1 + 0.03 then
        now1 = timer
        update()
    end if
    
    sleep 2

loop until multikey(&H01)