[Solved] jumper big maps want to optimise it using 'sectors'

[gcmartijn]

Hi

I'm trying to optimise the pathfinding code because it is to slow now.
Jumper needs only to search inside a x1,y1,x2,y2 rect.

My first though was this.

Code: Select all

-- some variables
-- targetX
-- targetY 
-- currentX 
-- currentY 
-- mapWidth = 4000
-- mapHeight = 768

-- this is for example the 'window/rect' where to do the pathfinding search
local x1 = 75
local y1 = 400
local x2 = 590
local y2 = 720
local w = x2 - x1
local h = y2 - y1
---

map = {}

for y = y1, y2 do
    map[y] = {}
    for x = x1, x2 do
        if collision(x, y) then
            map[y][x] = 1
        else
            map[y][x] = 0
        end
    end
end

local grid = Grid(map, true)
local myFinder = Pathfinder(grid, "JPS", 0)
myFinder:setHeuristic("MANHATTAN")

local path = myFinder:getPath(currentX, currentY, targetX, targetY)

But that will give me this error:

Code: Select all

jumper/grid.lua:78: Bad argument #1. Not a valid map
stack traceback:
	[C]: in function 'assert'
	lib/jumper/grid.lua:78: in function 'Grid'

So I guess the y and the x needs to be always 1.
But how to fix this problem ?

Thanks !

[MrFariator]

Looking at Jumper/core/assert.lua, it does indeed look like the library only accepts Array-maps, not arbitrary tables. I have never used Jumper myself, but I presume you could change your loop to be something like the following:

Code: Select all

map = {}

local mapY, mapX = 1, 1

for y = y1, y2 do
    map[mapY] = {}
    for x = x1, x2 do
        if collision(x, y) then
            map[mapY][mapX] = 1
        else
            map[mapY][mapX] = 0
        end
    end
    mapY = mapY + 1
    mapX = 1
end

[gcmartijn]

That gives me another error, the map is correct but the location is was not found [310, 437].

but the location is inside the given rect.
local x1 = 75
local y1 = 400
local x2 = 590
local y2 = 720

Code: Select all

local mapY, mapX = 1, 1

for y = y1, y2 do
    map[mapY] = {}
    for x = x1, x2 do
        -- if collision(x, y) then
        --     map[mapY][mapX] = 1
        --   else
        map[mapY][mapX] = 0
        --end
    end
    mapY = mapY + 1
    mapX = 1
end

...

jumper/pathfinder.lua:343: Invalid location [310, 437]
stack traceback:
	[C]: in function 'assert'

[MrFariator]

Oh, right, of course. To account for that you'll just have to fit the coordinates within the sector table's dimensions. Simply reduce the size of x2 and y2 by x1 and y1 respectively (assuming x1 and y1 will always be the top-left coordinates). Something like:

Code: Select all

-- after the for loop
x2 = x2 - x1 + 1
y2 = y2 - y1 + 1
x1 = 1
y1 = 1

Also, my previous post contained a little goof, gotta increment the mapX as well:

Code: Select all

for y = y1, y2 do
    map[mapY] = {}
    for x = x1, x2 do
        if collision(x, y) then
            map[mapY][mapX] = 1
        else
            map[mapY][mapX] = 0
        end
        mapX = mapX + 1 -- this line here
    end
    mapY = mapY + 1
    mapX = 1
end

[gcmartijn]

uuuh what do you mean with this ?

Code: Select all

-- after the for loop
x2 = x2 - x1 + 1
y2 = y2 - y1 + 1
x1 = 1
y1 = 1

After for y = y1, y2 do end ?
I don't use that variables anymore only the targetX/Y and currentX/Y the full code is this

Code: Select all

-- targetX
-- targetY 
-- currentX 
-- currentY 
-- mapWidth = 4000
-- mapHeight = 768

local function collision(x, y)
    ... 
    return false or true
end

map = {}

-- create a 'window' where to search
local x1 = 75
local y1 = 400
local x2 = 590
local y2 = 720

local mapY, mapX = 1, 1

for y = y1, y2 do
    map[mapY] = {}
    for x = x1, x2 do
        -- if collision(x, y) then
        --    map[mapY][mapX] = 1
        -- else
        map[mapY][mapX] = 0
        --end
        mapX = mapX + 1
    end
    mapY = mapY + 1
    mapX = 1
end

local grid = Grid(map, true)
local myFinder = Pathfinder(grid, "JPS", 0)
myFinder:setHeuristic("MANHATTAN")

local path = myFinder:getPath(currentX, currentY, targetX, targetY)
local p = {}
if path then
    print(("Path found! Length: %.2f"):format(path:getLength()))
    for node, _ in path:nodes() do
        table.insert(
            p,
            {
                x = node:getX(),
                y = node:getY()
            }
        )
    end
    return p
end

but still that error:
jumper/pathfinder.lua:343: Invalid location [310, 437]

[MrFariator]

The same principle from my previous reply still applies, just fit the targetX/Y and currentX/Y within the contraints of your sector, and convert it back the actual coordinates after you've done the pathfinding.

[gcmartijn]

Sorry I don't understand how... I saw something with a camera class that converts local to world coordinates and world to local.

I guess you I have to change after the for loop those 4 coordinate but what is the formula to do that ?

Code: Select all

currentX = currentX - x2
currentY = currentY - y2
targetX = targetX - x2
targetY = targetY - y2

local grid = Grid(map, true)
local myFinder = Pathfinder(grid, "JPS", 0)
myFinder:setHeuristic("MANHATTAN")

local path = myFinder:getPath(currentX, currentY, targetX, targetY)

[gcmartijn]

I think I understand it almost...
Experimenting with this.

Code: Select all

local currentXn, currentYn
local targetXn, targetYn

local mapY, mapX = 1, 1
for y = y1, y2 do
    map[mapY] = {}
    if currentY == y then
        currentYn = mapY
    end
    if targetY == y then
        targetYn = mapY
    end
    for x = x1, x2 do
        if currentX == x then
            currentXn = mapX
        end
        if targetX == x then
            targetXn = mapX
        end

        if collision(x, y) then
            map[mapY][mapX] = 1
        else
            map[mapY][mapX] = 0
        end
        mapX = mapX + 1
    end
    mapY = mapY + 1
    mapX = 1
end

currentX = currentXn
currentY = currentYn
targetX = targetXn
targetY = targetYn

And then I have to convert the path coordinates.

[gcmartijn]

Oke working code, but not the final code, because I have to figure out how to do the math to convert the xy data I create 3 tables...

Thanks for your help, I will mention it in the credits list

Code: Select all

map = {}

-- create a 'window' where to search
local x1 = 75
local y1 = 400
local x2 = 590
local y2 = 720

local mapY, mapX = 1, 1
local mapConvert = {}
local mapConvert2 = {}
for y = y1, y2 do
    map[mapY] = {}
    mapConvert[y] = {}
    mapConvert2[mapY] = {}
    for x = x1, x2 do
        mapConvert[y][x] = {mapX, mapY}
        mapConvert2[mapY][mapX] = {x, y}
        if collision(x, y) then
            map[mapY][mapX] = 1
        else
            map[mapY][mapX] = 0
        end
        mapX = mapX + 1
    end
    mapY = mapY + 1
    mapX = 1
end

local xy = mapConvert[currentY][currentX]
currentX = xy[1]
currentY = xy[2]
xy = mapConvert[targetY][targetX]
targetX = xy[1]
targetY = xy[2]

local grid = Grid(map, true)
local myFinder = Pathfinder(grid, "JPS", 0)
myFinder:setHeuristic("MANHATTAN")

local path = myFinder:getPath(currentX, currentY, targetX, targetY)
local p = {}
if path then
    print(("Path found! Length: %.2f"):format(path:getLength()))
    for node, _ in path:nodes() do
        xy = mapConvert2[node:getY()][node:getX()]

        table.insert(
            p,
            {
                x = xy[1],
                y = xy[2]
            }
        )
    end
end

[gcmartijn]

Solved

Code: Select all

local function collision(x, y)
....
end

map = {}

-- create a 'window' where to search
local x1 = 75
local y1 = 400
local x2 = 590
local y2 = 720
----- 

local mapY, mapX = 1, 1
for y = y1, y2 do
    map[mapY] = {}
    for x = x1, x2 do
        if collision(x, y) then
            map[mapY][mapX] = 1
        else
            map[mapY][mapX] = 0
        end
        mapX = mapX + 1
    end
    mapY = mapY + 1
    mapX = 1
end

currentX = currentX - x1 + 1
currentY = currentY - y1 + 1
targetX = targetX - x1 + 1
targetY = targetY - y1 + 1

local grid = Grid(map, true)
local myFinder = Pathfinder(grid, "JPS", 0)
myFinder:setHeuristic("MANHATTAN")

local path = myFinder:getPath(currentX, currentY, targetX, targetY)
local p = {}
if path then
    print(("Path found! Length: %.2f"):format(path:getLength()))
    for node, _ in path:nodes() do
        table.insert(
            p,
            {
                x = node:getX() + x1 - 1,
                y = node:getY() + y1 - 1
            }
        )
    end
end

Thanks for the helping