Problems implementing Jumper, and optimisation. [SOLVED]

[NemoVonFish]

I'm having some trouble implementing pathing in to a very rudimentary roguelike using Jumper. I'm not particularly attached to Jumper, so if it ends up not being the best thing for what i'm trying to do, changing isn't that much of an issue. That being said, here's the problem.

I can calculate a path, and detect when that path is below a certain value, and change them to "aggressive". My problem is once they're aggressive, I can't figure out how to, well, do the actual pathing.
The nodes aren't generated for every coordinate, so I can't just be like "move to the first step in the path.", there's a command to do that (path:fill()) But I have no idea where to put that, or when to run it.

My biggest problem, isn't actually an error, but generating a path every time it's the enemies turn to move, for each enemy, is going to lag the game, and at one point I had it kind of working, and there was a noticeable drop in the movement animation. I'm very, very new to programming, so I realise i'm going to be awful at optimisation. I'd appreciate anyone willing to take a look-see through the code, and point out anything I could do better.



Controls:

• Numpad 1-9 for movement.
• Numpad + to spawn an enemy.
• Numpad Enter to check who's "aggroed"

[Roland_Yonaba]

Hi NemoVonFish,

Nice project going on. I took a look at your code, and I can provide some interesting ideas.
Well, the lag that occurs is quite normal, here, because you are putting a very high load on the pathfinding.

First of all, let us consider this portion of our code:

Code: Select all

for i, v in ipairs(enemies) do
  if v.energy >= 1000  then -- Is it their turn?
    aggroProximity(v) -- Aggro them if they're within range.
    if v.aggressive == true then ... end
  end
end

And this, given that:

Code: Select all

function aggroProximity(foo) -- The pathing function.
  local walkable = 1
  local Grid  = require ("libs.jumper.grid")
  local Pathfinder = require ("libs.jumper.pathfinder")
  local grid = Grid(mapCurrent)
  local myFinder = Pathfinder(grid, 'JPS', walkable)
  local startx, starty = foo.grid_x/16, foo.grid_y/16
  local endx, endy = player.grid_x/16, player.grid_y/16
  local path = myFinder:getPath(startx, starty, endx, endy)
  if path then
    if path:getLength() < foo.sense then
      foo.aggressive = true
    end
  end
end

This is truly where the lag comes. Is it really needed to pathfind for each ennemy before
trying to guess if the ennemy is close enough to the player to attack him ?

I would suggest a different approach.
Since each ennemy has a "sense" area, you can loop through the collection of ennemies, and calculate the actual distance between
the ennemy and the player, and compare it to that "sense" value. As such, you can mark the ennemies that are "close enough" to
the player and let them use pathfinding. Here is an example, assuming "sense" is the radius of a circular area around the ennemy (in pixels, not in tile units).

Code: Select all

local function squareDistance(entityA, entityB)
  local dx = math.abs(entityA.x - entityB.x)
  local dy = math.abs(entityA.y - entityB.y)
  return dx*dx + dy*dy
end

for i, ennemy in ipairs(ennemies) do
  if v.energy >= 1000 then
    -- if the player is close enough to the ennemy
    if squareDistance(ennemy, player) <= (ennemy.sense*ennemy.sense) then 
      calculatePath(ennemy, player)
    end
  end
end 

Note: I am comparing the square distance to the square of square (since math.sqrt is a costful function). Tricky, but valid, since
a = b also means a*a = b*b.

EDIT: You can also try a lineOfSight algorithm. This will tell if the ennemy sees the player. It is a bit more expensive than the above, but still less explensive than performing a pathfinding request, actually. This feature is actually included in the latests commits of Jumper, but still in development.

The calculatePath function will actually do a similar job to what the old aggroProximity() was doing, but with a major difference.
You do not have to require the library, init a grid object and a pather each time. Just do that once, at the top of your script:

Code: Select all

  local walkable = 1
  local Grid  = require ("libs.jumper.grid")
  local Pathfinder = require ("libs.jumper.pathfinder")
  local grid = Grid(mapCurrent) -- mapCurrent has to be defined
  local myFinder = Pathfinder(grid, 'JPS', walkable)

Even if the world changes (for instance a tile/ a group of tiles becomes switches from walkable to unwalkable, Jumper will accomodate with that, so that to don't need to recreate a new grid.
That way, the calculatePath function will look like:

Code: Select all

local function worldToTile(entity, tileSize)
  return math.floor(entity.x/tileSize)+1, math.floor(entity.y/tileSize)+1
end

function calculatePath(entity, target)
  local sx, sy = worldToTile(entity,16)
  local ex, ey = worldToTile(target,16)
  local path = myFinder:getPath(sx, sy, ex, ey)
  if path then
    path:fill() -- the path filling you need, since you are using Jump Point Search finder
  end
  entity.path = path or false -- saves the path when found, false otherwise.
end

Note: The worldToTile function performs conversion from world coordinates to tile coordinates. Since your tile coordinates start at 1,1 (but not 0,0), you will have to add +1 in tile units to perform a correct conversion.

You can commit those changes, and see how the speed improves. Jumper was designed to provide different flavors of algorithms and speed for pathfinding on large grids. But, as you said, you are not tight to it, there are lots of implementations for pathfinding out there.

[NemoVonFish]

First of all, thank you so much for all of your help, I wasn't expecting such a lengthy reply, and I really appreciate you taking the time to help me out.

However, I haven't quite got it working. My last remaining issue should be quite simple. It's riiiiiight here:

Code: Select all

calculatePath(v, player)
if v.path == false then -- Can the enemy path to the PC?
	-- If not, then move randomly
	v.energy = v.energy - (v.moveCost / 2)
else
	-- Then take the first step
	npcMoveTo(v, x, y)
end

That npcMoveTo() function needs the x and y coordinates of the first step in the path, and despite pouring over the documentation, and looking through the source of the Jumper example, I can't find where to get them. I think it may be something to do with if node count = 1 then but i'm hoping i'm just silly and there's a much cleaner way to do it.

[Roland_Yonaba]

First of all, thank you so much for all of your help, I wasn't expecting such a lengthy reply, and I really appreciate you taking the time to help me out.

You are welcome.

That npcMoveTo() function needs the x and y coordinates of the first step in the path, and despite pouring over the documentation, and looking through the source of the Jumper example, I can't find where to get them.

The path returned from pathfinder:getPath(...) is an array of array values in its simple form. Just index in it. The first element is the starting node (the actual start position), the last element is the goal. So if you need the next step, you are looking for the #2 element.

Code: Select all

local nextMove = path[2]
npcMoveTo(entity, nextMove.x, nextMove.y)

[NemoVonFish]

Success! Pathing works perfectly now, they attack when they're right next to you, and there's no noticeable lag. I tried to attach the updated .love, but it says the quota has been reached. If anyone would like the functioning version, thanks to Roland_Yonaba, feel free to message me.

[Roland_Yonaba]

Success! Pathing works perfectly now, they attack when they're right next to you, and there's no noticeable lag. I tried to attach the updated .love, but it says the quota has been reached. If anyone would like the functioning version, thanks to Roland_Yonaba, feel free to message me.

Well, you can host it somewhere and share the link here.
Just for babbling, this gave me an idea (I filed an issue for it, so that i'll be working on it when I find some spare time).
I'll try to implement a line of sight in the Grid API. This will be very handy for situations like these. When you have a large set of units pathing at the same time, given that all those units are spread in different rooms, we may want to move only ennemies that are close enough to "see" the player.

Code: Select all

local function worldToTile(x,y,tileSize)
  return math.floor(x/tileSize)+1, math.floor(y/tileSize)+1
end

local rogueQueue = {}
for i, rogue in ipairs(rogues) do
  -- get startNode and endNode
  rogue.tileX, rogue.tileY = worldToTile(rogue.x, rogue.y, actualTileSize)
  local rogueNode = myGrid:getNodeAt(rogue.tileX, rogue.tileY)
  local player.tileX, player.tileY = worldToTile(player.x, player.y, actualTileSize)
  local playerNode = myGrid:getNodeAt(player.tileX, player.tileY)

  -- Does the actual rogue see the player ?
  if myGrid:isLineOfSight(rogueNode, playerNode) then
    rogueQueue[#rogueQueue+1] = rogue -- then we mark it for pathfinding
  end
end

for i, rogue in ipairs(rogueQueue)
  myFinder:getPath(rogue.tileX, rogue.tileY, player.tileX, player.tileY)
end