2

I am in need of some type of pathfinding, so I searched the Internet and found some algorithms.

It seems like they all need some type of map also. This map can be represented by:

  • Grid
  • Nodes

As my map is currently quite huge (20.000 x 20.000 px), a grid map of 1 x 1 px tiles would lead to 400.000.000 unique points on the Grid and also the best Quality I would think. But thats way to much points for me so I could either

  • increase the tile size (e.g. 50 x 50 px = 160.000 unique points)
  • switch to Nodes

As the 160.000 unique points are also to much for me, or I would say, not the quality I would like to have, as some units are bigger as 50 px, I think Nodes are the better way to go.

I found this on the Internet 2D Nodal Pathfinding without a Grid and did some calculations:

local radius = 75                               -- this varies for some units so i stick to the biggest value
local DistanceBetweenNodes = radius * 2         -- to pass tiles diagonaly
local grids = 166                               -- how many col/row
local MapSize = grids * DistanceBetweenNodes    -- around 25.000
local walkable = 0                              -- used later

local Map = {}

function even(a)
    return ((a / radius) % 2 == 0)
end

for x = 0, MapSize, radius do
    Map[x] = {}
    for y = 0, MapSize, radius do
        if (even(x) and even(y)) or (not even(x) and not even(y)) then
            Map[x][y] = walkable
        end
    end
end

Without removing the unpassable Nodes and a unit size of 75 i would end up with ~55445 unique Nodes. The Nodes will drastically shrink if i remove the unpassable Nodes, but as my units have different sizes i need to make the radius to the smallest unit i got. I dont know if this will work with bigger units later then.

So i searched the Internet again and found this Nav Meshes. This will reduce the Nodes to only "a few" in my eyes and would work with any unit size.

UPDATE 28.09 I have created a nodal Map of all passable Areas now ~30.000 nodes.

Here is an totally random example of a map and the points i have: Example Map

1
  • Updated First Post.
    – LuaNoob
    Sep 26, 2016 at 12:01

1 Answer 1

2

This calls for some optimization, and reduce the amount of nodes you have.

Almost any pathfinding algorithm can take a node list that is not a grid. You will need to adjust for distance between nodes, though.

You could also increase your grid size so that it does not have as many squares. You will need to compensate for small, narrow paths, in some sort of way, though.

At the end of the day, i would suggest you reduce your node count by simply placing nodes in an arranged path, where you know it is possible to get from point A to B, specifying the neighbors. You will need to manually make a node path for every level, though. Take my test as an example (There are no walls, just the node path):

enter image description here

For your provided map, you would end up with a path node similar to this:

enter image description here

Which has around 50 nodes, compared to the hundreds a grid can have.

This can work on any scale, since your node count is dramatically cut, compared to the grid approach. You will need to make some adjustments, like calculating the distance between nodes, now that they are not in a grid. For this test i am using dijkstra algorithm, in Corona SDK (Lua), but you can try using any other like A-star (A*), which is used in many games and can be faster.

I found a Unity example that takes a similar approach using nodes, and you can see that the approach works in 3D as well:

enter image description here

6
  • I've added an example to my Post to show what Points i have.
    – LuaNoob
    Sep 25, 2016 at 16:55
  • just saw this and calculating how much nodes i would need: jgallant.com/…
    – LuaNoob
    Sep 25, 2016 at 17:06
  • That seems like another good approach. You can make your grid smaller so that you end up with less nodes. Sep 25, 2016 at 17:22
  • Yeah compared to the 1px version with 400.000.000 nodes this would produce: (25.000 / unit.width * 2) * (25.000 / unit.width * 2), while unit.width ~ 75 for example ===> ~30.000 nodes. I just need to look how i put them into Diamond Shape.
    – LuaNoob
    Sep 25, 2016 at 17:32
  • Why not try it the grid way, but just make your grid smaller, like every grid square be 20 px? Sep 25, 2016 at 17:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.