[RMMV Plugin] Pathfinding Extras

Version: v1.00

Introduction

Unlike in RPG Maker VX Ace and former, RPG Maker MV's default game system allows the player to click on a game map tile as destination. The player character will find a shortest path to it using A* pathfinding algorithm, as implemented in method Game_Character.findDirectionTo.

In this plugin, such that method is overriden and extended to allow you to select one of pathfinding algorithms: A*, Jump-point Search, Dijkstra and Greedy Best-first Search. Additionally, you can also enable the characters to move diagonally by setting the parameter '8-directional Mode'.

Contact me for support/bug report:

listra92@gmail.com
https://www.facebook.com/don.listRA92

About Pathfinding Algorithms

You can learn about the pathfinding algorithms in the following articles.

A*:

Jump-point Search:

Dijkstra:

Features and Usages

  • Option to select other pathfinding algorithms to experiment: Jump-point Search, Dijkstra and Greedy Best-first Search.
  • Option whether to keep the found path until the character reach the destination; thus the pathfinding algorithm is only executed once when being ordered to move to the destination. However, the path can be obstructed by some moving objects (other characters), as the character won't move avoiding them.
  • Option whether to draw diagnostic traces as magenta and blue squares that represent path and explored tiles.

Notes

  • If you have MK_AdvancedMove plugin installed, put this plugin under it.
  • Jump-point search is the fastest algorithm since it searches fewer tiles than A* does, but still produces shortest path.
  • Greedy best-first search often performs badly; it tends to produce much longer path. Also unless the 'Remember Path' option is enabled, the character's movement can somewhat get stalled.

Coming in the Next Version

  • Some optimizations, probably.

Known issues

  • The current implemented jump-point search somehow fails on dealing with some certain tiles, like in sample map 'School Hall'.

Download Plugin

MK_Pathfinding.js

4 comments:

  1. Thks a lot for this. I was wondering if we could store in a variable the number of steps needed to reach the destination without moving anything ? A script call which will return the number of steps required for event A to reach tile(x, y)without moving the event A?

    ReplyDelete
    Replies
    1. Sorry for late reply, for instead just add the following script:

      this.character(0).findDirectionTo(goalX, goalY);
      $gameVariables.setValue(1, this.character(0)._pathl);

      Delete
  2. Thks a lot for this. I was wondering if we could store in a variable the number of steps needed to reach the destination without moving anything ? A script call which will return the number of steps required for event A to reach tile(x, y)without moving the event A?

    ReplyDelete