Page 1 of 1
[Solved] jumper big maps want to optimise it using 'sectors'
Posted: Fri Dec 25, 2020 8:56 am
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 !
Re: jumper big maps want to optimise it using 'sectors'
Posted: Fri Dec 25, 2020 10:09 am
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
Re: jumper big maps want to optimise it using 'sectors'
Posted: Fri Dec 25, 2020 10:20 am
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'
Re: jumper big maps want to optimise it using 'sectors'
Posted: Fri Dec 25, 2020 10:31 am
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
Re: jumper big maps want to optimise it using 'sectors'
Posted: Fri Dec 25, 2020 10:43 am
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]
Re: jumper big maps want to optimise it using 'sectors'
Posted: Fri Dec 25, 2020 11:27 am
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.
Re: jumper big maps want to optimise it using 'sectors'
Posted: Fri Dec 25, 2020 11:44 am
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)
Re: jumper big maps want to optimise it using 'sectors'
Posted: Fri Dec 25, 2020 12:10 pm
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.
Re: jumper big maps want to optimise it using 'sectors'
Posted: Fri Dec 25, 2020 12:32 pm
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
[Solved] Re: jumper big maps want to optimise it using 'sectors'
Posted: Fri Dec 25, 2020 6:14 pm
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