Eric: The Mysterious Stranger - RTS game(WIP)

[leopardpm]

OK, I watched your demo (looks great BTW!) I saw some special circumstances. Lets see if I can describe the issue I am talking about:


OK, two agents shown in picture: RED star and BLUE star. The green dotted line is the path of the RED agent. Some obstacles (houses and bushes) with their respective blocking tiles filled with yellow. Now, think just about the RED star agent moving.... when this agent starts moving diagonally past the 2nd bush, there should be no collisions even though the pixels and/or the collision rectangle used for the agent will overlap the bush when passing diagonally. Same circumstance should occur when passing the BLUE star agent IF the BLUE star agent is not moving (he is just sitting there contemplating life or chopping wood/whatever). But, note, when the RED star guy diagonally passes the BLUE guy, their pixels and collision rectangles WILL collide! But this is not an actual collision to worry about. This false colliding issue will also occur if the BLUE star guy is moving. If we only worry about tile-based collisions, then these issues disappear.

[leopardpm]

Basically, as an agent is following a path, before moving towards the next tile (per pixel), it will 'grab' that destination tile and mark it as Blocked (for collision purposes) and mark the tile he is leaving as Unblocked. If the tile he is trying to 'grab' is already grabbed (blocked) by another agent, then this agent needs to re-path. That is the whole enchilada, no need for any 'sliding past' , or 'waiting' for the other agent to go by, or any other special circumstance as this algo will deal with almost all cases fluidly.

[Boromir]

My pathfinder would do this.


It looks bad having the agents cut diagonally in front of an obstacle as well as being unrealistic.

[BasicCoder2]

Basically, as an agent is following a path, before moving towards the next tile (per pixel), it will 'grab' that destination tile and mark it as Blocked (for collision purposes) and mark the tile he is leaving as Unblocked.

to
That was in the previous experimental code with the blue obstacle tiles. Although I have not implemented that in the current version I am now trying to do so.
.

[BasicCoder2]

@Boromir,

If you look at the paths they do not cut diagonally in front of an obstacle tile or between obstacle tiles diagonally next to each other. If the distance for collisions is used and set correctly then for sprite to sprite collisions there will be no collision between a stationary sprite and a moving sprite they will slip passed each other even if the corners of their rectangles overlap. I have used the sprite to sprite collision by distance below so you can see it in action with the radius set to 1/3 the tile size.

I disagree about the blue guy and the red guy not colliding. If the blue guy is moving they might collide just as two cars going through an intersection.

I have not added any code yet to deal with an actual collision. At this stage they simply pass through each other with the printed comment that they have collided.

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
'=========================================================================================

function testCollision2(b1 as AGENT,b2 as AGENT,r as integer) as boolean
    dim as single xd,yd,dd
    xd = b1.x-b2.x
    yd = b1.y-b2.y
    dd = sqr(xd^2+yd^2)
    if dd > r then
        return FALSE
    else
        return TRUE
    end if
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 testCollision2(agents(i),agents(j),TS\3) 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  'this is used to stop the action with a collision
    
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)

[Boromir]

@BasicCoder2
Nice pathfinding demo.
My comment about corners was in regard to leopardpm's image were the star agent diagonally cuts past a bush. The agents in my game look extremely bad if they are aloud to cut corners with each other. I experimented with that a while back.

[BasicCoder2]

@BasicCoder2
My comment about corners was in regard to leopardpm's image were the star agent diagonally cuts past a bush..

In the example with the blue obstacles that was the case. There was no check for it whereas a check is done by the path finder.
I have been experimenting with the selection of the next tile to move to as in the blue obstacle example with path following.
I thought if the agent finds a path blocked due to a cross over it can wait until it is unblocked. This would not work if moving along the same line in opposite directions for they would be waiting for the other to move which would never happen. I think maybe the easiest solution is going to be a side step and a recalculation of the path to the target.
.

[leopardpm]

ok, if you don't allow diagonal movement when at least one of the two crossed diagonals are blocked, then that solves most of the issues - especially if you make it so agents grab/block their next intended tile when they start their per pixel movement. If you grab/block BOTH the destination tile and the origination tile, then there will be basically no overlap at all during diagonal movement. Guess it depends on what you think looks good. In this close-up of showing how BC's solution differs from mine, I think it looks dopey when an agent turns 90 degrees takes 3 steps to a tile, then turns another 90 degrees to go around the obstacle without diagonals. But my solution of just plain diagonal movement then has the issue of too much overlap...


probably the mst realistic would be a combination... maybe more of a bezier/spline path... which would make everything 10 times more complicated and IMHO would not be worth it.

[leopardpm]

BC, here is what I do not understand about your method: what happens if two agents are both in their 'per pixel' movement between tiles and then their collision rectangles collide - you can't re-calc a path while inbetween, right? and if you make one guy stationary 'waiting' for the other to pass, then he is stuck if the other guys destination tile is his last tile on his path and he starts doing something else, right? It seems to me that while an agent is doing his special per pixel between tiles movement, he is kinda in a special state where he only has three options: (1) stay still, (2) go to destination tile, (3) go back to origination tile - and without 'grabbing/blocking' his destination tile from others potentially going there, then it seems his options become even more limited and unrealistic looking - both going backwards and pure stopping look wrong and awkward, right? I mean, people most often adjust their speed and direction when expecting an obstacle and very rarely just outright stop and wait while walking (though they do do this if their own personal path planner is sub-optimal! lol)

[BasicCoder2]

ok, if you don't allow diagonal movement when at least one of the two crossed diagonals are blocked, then that solves most of the issues - especially if you make it so agents grab/block their next intended tile when they start their per pixel movement.

Again don't confuse the path finding demo code with the other experimental code with the blue colored no walk tiles. It is the path planner that blocks diagonal movement past an obstacle.

If you grab/block BOTH the destination tile and the origination tile, then there will be basically no overlap at all during diagonal movement.

Nope in the blue obstacle demo it grabs the next tile and releases its current tile at the same time. You can see the next blue blocking tile jump ahead of the green border sprite and there are probably points where they overlap. Perhaps an example when they might overlap might be when they are next to each other horizontally and A chooses first and moves up/right and B chooses second and moves left.

Code: Select all

'+---+---+---+
'|   |   |   |
'+---+---+---+
'| A | B |   |
'+---+---+---+
'
'+---+---+---+
'|   | A |   |
'+---+---+---+
'| B |   |   |
'+---+---+---+

It seems to me that while an agent is doing his special per pixel between tiles movement, he is kinda in a special state

Exactly. They are all in that special state (moving between tiles) until they are all on their destination tile. At that point each chooses in turn its next tile or in the case of the path finder they select the next tile on the path list even if it means colliding and passing through another agent.

However the rest of your question refers to path following and as I wrote earlier the path following demo is not using that method of choosing the next tile. The next tile is taken off the path list. They just go through each other and simply print the fact they collided. And as I also pointed out that stopping to let the other guy pass could only work when a path crosses another path. When they are travelling in opposite direction along the same path one or both must step aside.

Like you guys I am interested in some simple but good looking solution. I find it an interesting puzzle to solve.

While looking for how others might have tackled the problem I see that getting patents on solutions is alive and strong,
https://www.google.com/patents/US5963218
.

[BasicCoder2]

After some time playing with different avoidance actions when a path following agent collides with another agent I have come to the conclusion the easiest method that worked for me was to simply to turn off the path finding and turn on the wander mode long enough for them to separate and then reset the path again.

This seems to be what you are trying to do?
Vikings war of clans
https://www.youtube.com/watch?v=VmBcWLrXjVQ
.

[Boromir]

This seems to be what you are trying to do?
Vikings war of clans
https://www.youtube.com/watch?v=VmBcWLrXjVQ
.

My goal is a RTS game but quite different from that.
I don't like the look of that graphics style or the gameplay system.
My goal is more like an age of empires 2 with role playing added.

[BasicCoder2]

My goal is more like an age of empires 2 with role playing added.

Watching some utube videos of that game I see the characters do not smooth their paths as Leopardpm suggests would make things look more natural. Certainly the graphics are good, no doubt due to the work of professional artists. I read that "all of the 2D sprites in AoE began life as 3D models". I see also there is a need for algorithms to handle group movements.

I think I have the agent to agent collision avoidance pretty much sorted it just needs a few more tweaks to make it look more natural. I will have to make an isometric display to see how it looks. It is probably the most important part of your game so far you need to implement as otherwise you seem to be making good progress with everything else.

.

[leopardpm]

I see also there is a need for algorithms to handle group movements.

I have never coded group movements beyond the basic 'boid flocking' stuff... I haven't really put much thought into it - but it would be important for troop formation movement for sure. I just figure is easiest to have each unit in a selected group path to its new position which would be relative to the clicked destination... based on the center of the group. In this way, each unit would find its own path and end up at exactly the right place... but it can look like a 'free for all' as each unit may choose very different paths depending upon the terrain and obstacles... oh well...

[BasicCoder2]

There seems to be a lot of complicated solutions to group movement however what you write makes perfect sense to me. Each agent knows its place and yet can deal with obstacles all on its own. Although I don't have time to do it today I will get some agents working together the way you suggest particularly now I have the agent to agent collision sorted.
.