C
C#•3d ago
Theos

Optimize graph generation for 2D grid

Hey, I'm working on a 2D game. Right now I'm adding enemies and decided to use A* for their pathfinding. Player can place/destroy tiles so the graph needs to be updated based on that. I was thinking about placing path nodes above each tile and connect them with their neighbors. The hardest part is making connections that require enemies to jump. Only approach that comes to my mind is something like this (pseudocode): 
foreach node in nodes
  var nodesInRange = GetNodesInRange(range)
  foreach nodeInRange in nodesInRange
    if(canJumpTo(from: node, to: nodeInRange)) node.addConnection(nodeInRange, type: jump)
foreach node in nodes
  var nodesInRange = GetNodesInRange(range)
  foreach nodeInRange in nodesInRange
    if(canJumpTo(from: node, to: nodeInRange)) node.addConnection(nodeInRange, type: jump)
I would somehow need to check if jump is possible, based on monster's jump power, mass and gravity. Monsters can have different sizes and jump powers so I would need to calculate graphs for each monster separately. Each tile place/destroy means recalculating the graph. Also I can't generate graph for the whole world because world is huge (4096x4096 tiles), so I would need to generate graph for only some chunk of the map, and then when the monster moves generate graph again for the new terrain thats in range. There is a lot of problems and I'm not sure how to approach it. Could you guide me a bit? Thanks!
No description
1 Reply
Anton
Anton•3d ago
1. compute lazily 2. cache 3. make terrain change invalidate the cache should be enough if it's not enough, you'll need to make something more specific for the problem either be careful about invalidation or update the graph based on deltas to the world (or both) but only do this if a basic cache is not enough because it's going to be way more complicated

Did you find this page helpful?