I have a 2d grid map that contains hostile npcs with a custom pathfinding. They currently use raycast on each node to check obstacles and reach players or items. I would like to know if it would be better for performance to instead create an array of coordinates that hold values like obstacles and check them instead. (Example: if grid[x][z] and not grid[x][z]["Obstacle"] then --[[walk there]]-- end)
✓ ANSWER ACCEPTED
What's better for performance: raycast or array check?
1 answer
✓ Accepted answer
Raycasting would do more calculations, but it would also run those calculations in C++, whereas your algorithm runs in Lua (which is much slower), so the it's hard to say which is faster without testing it (ex using os.clock()):
local start = os.clock()
-- perform the code you want to try out
print(os.clock() - start)
This discussion is preserved as it was. New answers, comments, and votes are closed.
4 comments
Maybe the arrray would be better then, because besides raycasting it also creates parts with specific properties to entitle checked nodes so they dont get rechecked, which might be the biggest reason for the lag (generating about 40 blocks and raycasting 200 times per path for a single bot).
Its not that much of a problem currenty because not so much people play the game, but it's a pvp system where they create rooms and can use up to 3 bots to play alone if they want, and if somehow a lot of people start playing it would become something like 14-30 bots i guess. Maybe I should have made a lobby system instead and make each server one game instead.
I made a test with two scripts on a 3x3 map. The first one used raycheck with whitelist to check an obstacle and took about 0.001 seconds to complete. The second method used a dictionary grid to check an obstacle (if grid[x] and grid [x][z] and grid[x][z]["Obstacle"] then), which took from 2e-07 to 4e-07, which is about 0.0000003 seconds. So the second option seems to be way faster.
Thanks for posting your findings. I expect raycasting might make more sense if your grid was larger (ie smaller per tile), ex 1000x1000 instead of 3x3.