Friday Fun Facts 002: Dijkstra Path Finding and Grid Tessellation

The Pathfinder rides steady with progress

Another week goes by in the development of, and some interesting game-play additions have been added to the game. For starters, I have finally added AI and objective nodes to the game. The primary goal of the game as it stands will be to pass over as many objective nodes as possible before being overcome by enemy AI. It’s a really simple concept, but there is a lot of strategy to dodging AI and reaching the objective. And this couples really well with the fast-paced game-play, which force the player to think on their feet about their path.

Undirected Traversal graph Improvements

This update I’ve made huge progress in improving the undirected graph that the player traverses. Firstly, I’ve successfully developed and implemented my very own Dijkstra path finding algorithm. It currently runs at O(nlog(n)) time, due to some nice indexing optimizations. It turns out that the path finding algorithm runs faster than I expected, and is pretty cheap processing-wise due to the function being threaded.

Shortest Path to objective node using Dijkstra alg. (red). Enemies as teal rectangles.

I’ve also worked on making the graph continuous. Now if you continue going in one direction, you’ll just end up right back where you started. This was really fun to implement, it’s implemented the same way tessellation for textures is: I take an instance of the grid, duplicate it and create eight instances of the grid about the real grid, triangulate the entire thing, and then remove any node that is not connected to a node in the real grid. When the player lands on one of the “unreal” nodes, the player is teleported to the unreal real node’s corresponding real counterpart. To maintain the illusion that the graph loops, I render all 9 graphs on my stage, and cull edges that are out of the line of sight of the camera.

Future Plans

I’m going to focus on fixing the graphics of my game over the next week for the next update, and one of the main objectives is to switch over from Pixi.js to Three.js, which will allow me to do more fancy 3D things that I wouldn’t be able to do in Pixi without racking my head around a lot of perspective transforms. One of the things I look forward to implementing is a perlin noise function to give my nodes some height. I think this would look stylistically cool. Anyway, as always, feel free to comment any thoughts or suggests on what I am building. Have a rocking Friday, everybody!