Updating Pathfinding API

14/02/18 00:16
  • As mentioned in yesterday's entry. I took steps today to redefine the API interface to support potential fields and also to support combinations of vector fields using combination functions. I was able to document the expected behavior of these functions in the API docs, but the actual implementation of these functions will have to wait until tomorrow.

Pathfinding Engine Update

12/02/18 22:57
  • A lot has happened since my last entry. Creating this pathfinding library has inspired me to also extract the UI framework I developed in the latest edition of Almost Anagrams into its own library. This will help immensely in future projects as well. For my path finding test project, I have pulled in this new UI framework and my existing Tile Engine and I now have a simple graphical maze with multiple goals that the actor can navigate to. The example is using vector fields (one per each goal) to navigate the actor to each goal. This seems to work very well, except in the case of 90 degree corners. In some cases, the actor will move diagonally into the wall and slide against the wall and around the corner. This is because the normal vector before each 90 degree corner points diagonally. This could be solved simply by only allowing axis-aligned vectors in the field. However, this has inspired another idea. While researching different methods for pathfinding, I have come across a number of methods which can result in vector fields. These include diffusion and potential fields. The thought occurred to me that I could combine these methods. For example, I could add a vector field based on potential fields which adds a repulsive force around walls. I could then sum the value from this vector field with my existing vector field to get a new vector that would result in guiding the actor toward the center of the hall rather than hugging the corners. One could imagine also adding vector fields based on diffusion as well. There is a high degree of potential flexibility in this approach. I could combine as many fields as I need to and even define how each field influences the resulting vector (addition, subtraction, etc.). Tomorrow I plan to focus on adjusting my pathfinding API to incorporate potential fields and accommodate customized "blending" of fields.
  • I did record the corner hugging behavior mentioned above. I may post it later or include it in a summary video as a postmortem at a later date.

Pathfinding Engine

29/01/18 23:31
My current project has the need for robust pathfinding. This pathfinding needs to be efficient, allow for dynamic changes to the environment, and be able to guide large numbers of actors. I have decided to implement my own library to handle this, and I plan to release this as another plugin for Corona SDK. Today, I accomplished the following:

  • Drafted initial design in UML.
  • Decided to use ldoc to auto-generate the API documentation and incorporated it into my build script.
  • Implemented wavefront algorithm.
  • Implemented vector field algorithm.
  • Set up a test project to enable interactive manual testing of the library.