Improve pathfinding performance by searching submaps

[boneskull]

I don't have a fully working example of this yet, but this is the idea. AStar takes a map and will find paths. However, we can significantly increase performance if we only want to find a path within a subset of that map.

Example:

The ground is made of impassable and passable tiles. I have a character on a tile. His range is 4; he can only move four tiles in any direction (up/down/left/right/diagonal). Some subset of these tiles may be impassable, and thus it may be impossible for the character to reach a tile within 4 spaces, because the path to get there may be longer than the range.

I need to compute these paths. But there's no need to search the whole map to get them, since the character only has a range*2+1 size square to possibly move within.

Solution is below, but it's not quite ideal and I'm unsure the best way to get around it. findPathInMap() returns an AStar instance, and you have to handle these manually (and call update() on them during ticks) in order for the paths to actually get found. Plus there's obviously some translation that needs to map the coordinates in the original map to the new, smaller map.

Another solution I was considering was another condition type where you could constrain the condition to different shapes. For example, you could say "this tile must be in group x AND the tile must be within rect y". How does that sound?

Usage is something like this:

var map = this._gridModel.getMap().getSubmap(x, y, w, h);
this._gridModel.findPathInMap(map, startX, startY, endX, endY, conditions, cb);

Anyway, here's the current diff. A side-effect is that the fromJSON() method now allows you to take slices of it, which may or may not be useful elsewhere:

diff --git a/models/GridModel.js b/models/GridModel.js
index 2113250..8570f06 100644
--- a/models/GridModel.js
+++ b/models/GridModel.js
@@ -167,6 +167,12 @@ exports = Class(function () {
        this._aStar.findPath(startX, startY, endX, endY, conditions, cb);
    };

+    this.findPathInMap = function(map, startX, startY, endX, endY, conditions, cb) {
+        var aStar = new AStar({map:map});
+        aStar.findPath(startX, startY, endX, endY, conditions, cb);
+        return aStar;
+    };
+
    this.scrollLeft = function (speed) {
        var data = this._data;
        var didScroll = false;
diff --git a/models/map/Map.js b/models/map/Map.js
index bf767b6..82ee849 100644
--- a/models/map/Map.js
+++ b/models/map/Map.js
@@ -15,16 +15,19 @@
  * You should have received a copy of the GNU General Public License
  * along with the Game Closure SDK.  If not, see <http://www.gnu.org/licenses/>.
  */
-exports = Class(function () {
+var Map = exports = Class(function () {
    this.init = function (opts) {
        var width = opts.width;
        var height = opts.height;
        var layers = opts.layers.length;
        var grid = [];
+       var tileY = opts.startY || 0;
+       var tileX = opts.startX || 0;
+       this._opts = opts;

-       for (var tileY = 0; tileY < height; tileY++) {
+       for (tileY = 0; tileY < height; tileY++) {
            var line = [];
-           for (var tileX = 0; tileX < width; tileX++) {
+           for (tileX = 0; tileX < width; tileX++) {
                var tile = [];
                var i = layers;
                while (i--) {
@@ -745,20 +748,20 @@ exports = Class(function () {
        return data;
    };

-   this.fromJSON = function (data) {
+   this.fromJSON = function (data, tileX, tileY, w, h) {
        var grid = [];
-       var width = data.header.width;
-       var height = data.header.height;
+       var width = w || data.header.width;
+       var height = h || data.header.height;
        var layers = data.header.layers;

        var dataGrid = data.grid;
+       for (y = tileY || 0; y < tileY + height; y++) {

-       for (var y = 0; y < height; y++) {
            var dataGridStr = dataGrid[y];
            var gridLine = [];
            var index = 0;

-           for (var x = 0; x < width; x++) {
+           for (x = tileX || 0; x < tileX + width; x++) {
                var gridTile = [];

                for (var i = 0; i < layers; i++) {
@@ -784,4 +787,11 @@ exports = Class(function () {
        this._height = height;
        this._layers = layers;
    };
+
+   this.getSubmap = function getSubmap(x, y, w, h) {
+        var json = this.toJSON(),
+            map = new Map(this._opts);
+        map.fromJSON(json, x, y, w, h);
+       return map;
+   };
 });
\ No newline at end of file

[boneskull]

It occurs to me the pathfinder doesn't make diagonal paths...heh

[boneskull]

At any rate playing more with this it seems we'll need to transpose the map, or something, because pathfinding becomes confused about what tiles are where...

[boneskull]

I think there may be an issue with the algorithm. I was able to use the algorithm from https://github.com/bgrins/javascript-astar to get my pathfinding working with proper condition evaluation.

This algorithm is synchronous of course and while it's fine for finding paths in say a 9x9 grid, I imagine there are performance issues when applied to larger maps.

[ArnoVanDerVegt]

Hello Chris, I thought about limiting the range of the path finding as well but wanted to add it it to the astar code. The submap creates a lot of new object instances for each search, you also need an astar instance for each search.

The easiest way to add a range limit in the current code is probably in the function: "this._valid = function (tileX, tileY)" which cuts off all tiles at a certain distance from the start position and limits the search...