Pathfinding Engine Update

  • 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.