Hello folks,

I am working on a new version of my in which I improve basically any aspect of the game. Each spaceship has a set of rooms that are connected to each other. Characters can walk freely to any non-obstructed area in the spaceship to repair stuff, heal their colleagues, etc.

Until now, I use pre-generated graphs for each room available in the game. When the game starts, I import the pre-loaded graphs and connect them on the edges. This works perfectly fine. However, I stored the graphs in generated source code files resulting very very large files. In addition, finding a path (A* algorithm) in very large environments could take a very long time - I use the same approach for dungeons.

I wanted to get rid of the large code files containing my graphs, make the creation process of the graph simpler and the path finding faster. After doing some heavy thinking, I came up with this idea:

• I do not store any graph information anywhere! (So I get rid of my large files)
• Instead, when starting the game, I take a black canvas and paint a rectangle in the size of the room for each room on my spaceship (or dungeon).
• Next, I paint all pixels black that lie inside walls, doors or objects. This is very easy and fast, because I store the bounding box for any object and all I have to do is to paint a black polygon on the canvas for each bounding box.

This takes around 80ms for the largest spaceship in my game, is 100% dynamic, fail-proof and fast. I also do not need to store a complex graph. All I have is an image where each white pixel is a location where a character can walk.

However, I ran into an issue: performance for pathfinding. The higher the resolution of my image, the larger is the graph. And the A* algorithm takes its time in large graphs. If I reduce the resolution, the graph is not as exact as I need it to be.

I wanted to ask for your ideas how to speed the pathfinding up?

I tried building a graph on top of my graph in which I connect the center of all rooms to the adjacent rooms. This way, my algorithm would only search along the correct direction. While this spees pathfinding up, it takes a few second to generate this additional graph and it also adds a lot of complexity.

An iterative GPU flood fill can count adjacent texels up or down for whatever your requirements are. It can be done as a pixel shader draw or in compute. The number of passes required to flood the map is related to the resolution of the texture and ‘seeding’ the map well can really get the count down. There are fancy terms for presetting A* using various techniques but I'm not up on all the different types.

If you are trying to navigate rooms then you might want to consider something other than brute force A* as you just need to go from entryway to entryway. There was an article about this on this site about 6 months ago from memory and probably has NavMesh in the title.

Assuming that obtaining a map of passable and impassable little squares from your levels is a solved problem, your task is A* pathfinding on a very large but mostly unobstructed square grid map.

There are various algorithms to do it quickly and exactly taking advantage of the grid structure and uniform costs in the pathfinding graph, for example “jump point search" (see Wikipedia) which is based on the insight that out of many equivalent optimal paths you can restrict the search to the ones that go straight as much as possible (up to walls, corners and other “jump points”) thus operating on a vastly reduced search space.

Thank you very much for your feedback. I will test it later this week! Especially Jump Point Search looks very promising, because I already have the perfect grid to operate on.

I started reading the paper about Jump Point Search yesterday and implemented it into my game engine. It was a great tip! Thank you very much, LorenzoGatti! I already had an image created that I wanted to use as graph, so the algorithm was perfect for me. I did some testing with the largest ships in my game. Creating the graph takes ~130ms which is done only when starting the game or when the players retrofits his/her ship. Creating the image-based graph is very fast, dynamic and super easy to store. This alone would be major advantage to my previously used strategy. After implementing Jump Point Search, searching for the longest possible path in the largest ship takes up to 120ms. Using the same graph with A* was around 3s! You do not feel the computational delay, so navigating in ships is fine. I will test dungeons in the next days which are much larger. If the algorithm performs similar to ships, then I am done! :-)