Bump and different speed units

pie · November 2017

Hi, I am building a tower defence like game, and trying to keep it simple I have not used (yet) any kind of collision detection except collidesWith - the simplest collision detection function for gideros.

my enemy units move toward waypoints placed manually at the corner of the streets on a tilemap: the waypoints have id numbers and some property, and a simple AI chooses where the unit should go next.
Everything is fine, but i tried using bump to avoid units overlapping and it looks better, however I had to give up because I have different speeds between units, and each unit could be "frozen" or "slowed" for a certain amount of time, blocking the other units on the same path (they move on a specific axis only, and it is the same as the waypoints - which are axis aligned between them since they are built on purpose along straight lines).
To decrease units speed I skip some frames in the move() function of the unit, this way I can move units slower than 1 px/frame.
The issue is that above a certain number of units stuck together, the spawning others are moved on the other side of the queue (after the "frozen unit" - in the direction where it was going) but they still think they have to reach a waypoint which is placed well before their current position (and they should do this, because there may be different paths to take). They are already bumping with the frozen one - which could also be unfrozen right now but it won't move because the others are pulling in the opposite direction to reach the previous waypoint... I don't know if I explained the issue well.. let me know

However, I was wondering if it could be possible to filter collisions between units with different speeds (my frame skip feature is bound to a speed property so I can check if speed[1]>speed[2]) in some way that the faster unit could overlap with the slower one and get through it without issues. The best thing would be that while overlapping it moves by some pixel aside.. but I am still thinking on how to do this: it should not be cpu killing.
Does anyone had the same problem? How did you solve it?

Thank you

antix · November 2017

@pie, there are a few approaches that I can think of.

If you are using a grid system to find paths for your units you could always set the grid cell of each unit to a solid state so when other units are path finding they will not enter that cell. This would most likely work but you would have to be performing a lot more path finding which would eat CPU time. Something like this maybe..

MAP_WIDTH = 100 -- number of horizontal cells
MAP_HEIGHT = 100 -- number of vertical cells
CELL_SIZE = 64 -- how large each cell is
 
array = {}
 
-- generate the 2d array that determines which cells are blocked or clear
for r = 1, MAP_HEIGHT do
  local row = {}
  for c = 1, MAP_WIDTH do
    row[#row + 1] = 0
  end
  array[#array + 1] = row
end
 
-- create 64 game units
local x, y = 32, 32
local units = {}
for i = 1, 64 do
  local u = {
    position = {x = x, y = x},
    arrayPos = {r = 0, c = 0}
  }
  units[#units + 1] = u -- save unit
  x, y = x + CELL_SIZE, y + CELL_SIZE
end
 
local function findPath(u)
end
 
local function moveUnit(u)
end
 
-- maintain unit position in 2d array
local function updateArrayPosition(u)
  -- get old position in array
  local a = u.arrayPos
  local ar, ac = a.r, a.c
 
  -- determine current position in array
  local p = u.position
  local r = p.y % CELL_SIZE
  local c = p.x % CELL_SIZE
 
  if r == ar and c == ac then
    -- the unit occupies the same cell, do nothing
  else
    -- mark previous cell unoccupied
    array[ar][ac] = 0
    -- mark current cell occupied
    array[r][c] = 1
  end
end
 
local function onEnterFrame(e)
  local dt = e.deltaTime
  for i = #units, 1, -1 do -- reverse through list for easy removal
    local u = units[i]
    updateArrayPosition(u)
    findPath(u)
    -- etc, etc
  end
end
 
stage:addEventListener(Event.ENTER_FRAME, onEnterFrame)

There is a fantastic resource called The Nature Of Code which covers things like this. This chapter covers agents that move about and at 6.11 you will see he talks about things not bumping into each other. There's a YouTube channel for the book too and it's a pretty good watch.

There is some flocking behavior code here in Lua that can be modified to work in Gideros (it's Lua code so 99% of the work is done). In The Nature Of Code, flocking is discussed at 6.13

The only issue is how much CPU time this eats. In my own experiment with this kind of thing I stagger the checks between game objects. By stagger I mean game objects only calculate avoidance every n frames like this..

local frameCount = 1
local maxFrames = 8
 
-- increment and reset a framecounter
local function incrementFrame()
  local frameCount = frameCount + 1
  if frameCount > maxFrames then frameCount = 1 end
  frameCount = frameCount
  return frameCount -- always returns a number between 1 and maxFrames
end
 
-- our pretend game objects
local units = {}
 
-- create 64 units
for i = 1, 64 do
  local unit = {
    position = {x = 0, y = 0},
    velocity = {x = 0, y = 0},
    frame = incrementFrame(), -- get a number (1-8)
  }
  units[#units + 1] = unit -- save unit
end
 
local function avoidOtherUnits(u)
end
 
local function onEnterFrame(e)
  local dt = e.deltaTime
  for i = #units, 1, -1 do -- always reverse through lists of game objects for easy removal
    local u = units[i]
    if u.frame == frameCount then -- only run code every maxFrames frames
      avoidOtherUnits(u)
    end
    -- etc, etc
  end
 
  incrementFrame() -- increment frameCounter for next frame
end
 
stage:addEventListener(Event.ENTER_FRAME, onEnterFrame)

Generally when using avoidance code (and a lot of other code too) you don't need to check against every single other game object so you can use the handy queryRect in bump to get just the ones nearby..

local p = u.position
 
-- returns true only if the item is an enemy and NOT the unit doing the check
local function enemyFilter(item)
  if item.isEnemy and item ~= u then
    return true
  end
end
 
-- get all enemy items (not the current enemy though) within the rectangle
local items, len = bump:queryRect(p.x - 100, p.y - 100, 200, 200, enemyFilter)
if len > 0 then
  -- we now have a table of nearby units we want to avoid <img class="emoji" src="https://forum.giderosmobile.com/resources/emoji/smile.png" title=":)" alt=":)" height="20" />
  calculateAvoidance(items)
end

Hope that helps a little at least

pie · November 2017

Thank you, unfortunately I am not using a grid to move, just the coordinates of the waypoints - which are placed using a grid, but it's just accessory

I like bump:queryRect, I didn't saw it :-B I will give it a try

antix · November 2017

@pie darn, that makes things a little trickier.

Have you seen the bump function to query a segment (line)???

local items, len = world:querySegment(x1,y1,x2,y2,filter)

I wonder if you could project a line out in front of a unit and if there is another object that intersects with it (meaning the object will be blocked) then take appropriate steering action.

So project a line out in front and check. If there is nothing there then keep moving forward. If the line is intersected by another object, and that object is moving slower than this object, then steer away in some direction.

I think that might be a solution. Let us know if you can't figure it out

also.. this github page for the original bump.lua is a fantastic document

https://github.com/kikito/bump.lua

pie · November 2017

Good idea thanks, I'll try And see if it's not a CPU killer

antix · November 2017

Let us know how you get on

Howdy, Stranger!

Categories

In this Discussion

Top Posters

Bump and different speed units

Comments

Howdy, Stranger!

Quick Links

Categories

In this Discussion

Top Posters

Bump and different speed units

Comments