I am currently working on implementing a pathfinding module for my 2D game engine that I am writing in Python using Pygame.

Currently there are objects such as trees or buildings which can be placed in the game world which the game character should pathfind around. I am adding nodes to the corners of these objects because it's really the corners that are of interest. If there is a clear path to the goal then no pathfinding is needed.

However I am not sure how to connect all my nodes. Using a grid it's simple to define a nodes neighbors but with nodes spread out with varying distances a node can easily have 10 or even more neighbors. I am worried of performance issues if I simply add every single node in "line of sight" of each other as neighbors.

Anyone got some ideas?

  • \$\begingroup\$ This is often solved by implementing a nav mesh — have you looked into this? \$\endgroup\$
    – DMGregory
    Commented Nov 11, 2022 at 19:57
  • \$\begingroup\$ I've sumbled upon it but not really. Do you know any good guides or such that I can apply on python? From what I've seen it's mostly in Unity etc and I don't know any game engine yet. \$\endgroup\$
    – Zoler1337
    Commented Nov 11, 2022 at 20:56
  • \$\begingroup\$ Searching for "python nav-mesh" seems to turn up quite a few leads. \$\endgroup\$
    – DMGregory
    Commented Nov 11, 2022 at 21:17
  • \$\begingroup\$ Thanks for the help! Do you think there is any way to connect my nodes in a smarter way and thus reducing the complexity or is it fruitless? \$\endgroup\$
    – Zoler1337
    Commented Nov 11, 2022 at 21:47
  • \$\begingroup\$ I think a navmesh is a smarter and lower-complexity way to connect your nodes. Your current nodes become the corners of convex polygons, and you can A* over the polygon adjacency graph. This simplifies a clique of many nodes that all have line of sight to each other into a single unit representing a whole swath of traversable area. \$\endgroup\$
    – DMGregory
    Commented Nov 11, 2022 at 21:50


You must log in to answer this question.

Browse other questions tagged .