title: Pathfinding On a huge Map
body: <p>I am in need of some type of pathfinding, so I searched the Internet and found some algorithms.</p>
  
  <p>It seems like they all need some type of map also.
  This map can be represented by:</p>
  
  <ul>
  <li>Grid</li>
  <li>Nodes</li>
  </ul>
  
  <p>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 <strong>400.000.000</strong> 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 </p>
  
  <ul>
  <li>increase the tile size (e.g. 50 x 50 px = 160.000 unique points)</li>
  <li>switch to Nodes</li>
  </ul>
  
  <p>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.</p>
  
  <p>I found this on the Internet <a href="http://www.jgallant.com/nodal-pathfinding-in-unity-2d-with-a-in-non-grid-based-games/" rel="nofollow">2D Nodal Pathfinding without a Grid</a> and did some calculations:</p>
  
  <pre><code>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
  </code></pre>
  
  <p>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.</p>
  
  <p>So i searched the Internet again and found this <a href="https://drpexe.com/a-pathfinding-using-navmesh/" rel="nofollow">Nav Meshes</a>.
  This will reduce the Nodes to only "a few" in my eyes and would work with any unit size.</p>
  
  <p><strong>UPDATE 28.09</strong>
  I have created a nodal Map of all passable Areas now ~30.000 nodes.</p>
  
  <p>Here is an totally random example of a map and the points i have:
  <a href="http://i.stack.imgur.com/kjJrU.png" rel="nofollow">Example Map</a></p>