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

Questions about the LÖVE API, installing LÖVE and other support related questions go here.
Forum rules
Before you make a thread asking for help, read this.
Post Reply
gcmartijn
Citizen
Posts: 51
Joined: Sat Dec 28, 2019 6:35 pm

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

Post by 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 !
Last edited by gcmartijn on Fri Dec 25, 2020 6:14 pm, edited 1 time in total.
MrFariator
Party member
Posts: 243
Joined: Wed Oct 05, 2016 11:53 am

Re: jumper big maps want to optimise it using 'sectors'

Post by 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
Citizen
Posts: 51
Joined: Sat Dec 28, 2019 6:35 pm

Re: jumper big maps want to optimise it using 'sectors'

Post by 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
Party member
Posts: 243
Joined: Wed Oct 05, 2016 11:53 am

Re: jumper big maps want to optimise it using 'sectors'

Post by 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
Citizen
Posts: 51
Joined: Sat Dec 28, 2019 6:35 pm

Re: jumper big maps want to optimise it using 'sectors'

Post by 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
Party member
Posts: 243
Joined: Wed Oct 05, 2016 11:53 am

Re: jumper big maps want to optimise it using 'sectors'

Post by 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
Citizen
Posts: 51
Joined: Sat Dec 28, 2019 6:35 pm

Re: jumper big maps want to optimise it using 'sectors'

Post by 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
Citizen
Posts: 51
Joined: Sat Dec 28, 2019 6:35 pm

Re: jumper big maps want to optimise it using 'sectors'

Post by 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
Citizen
Posts: 51
Joined: Sat Dec 28, 2019 6:35 pm

Re: jumper big maps want to optimise it using 'sectors'

Post by 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
Citizen
Posts: 51
Joined: Sat Dec 28, 2019 6:35 pm

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

Post by 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
Post Reply

Who is online

Users browsing this forum: No registered users and 44 guests