Pathfinding in a Tilemap

Instructions

Click the map to place the start and goal nodes. Then select the tree search algorithm, and click the step button to advance the search.

The results of each pass through the tree search algorithm will be printed in the frontier and explored areas, respectively. Additionally, as nodes are added to the frontier, they will also be marked on the map as yellow discs. The numbers on the discs indicate:

1. The path cost to reach this node
2. The straight-line distance to the goal
3. A heuristic formed by adding these values

Tree Search Approaches

The algorithms this example employs are:

Breadth-first The frontier is processed in the order nodes are expanded.

Greedy The shortest path (in terms of movement cost) on the frontier is processed first.

Best-first The path ending closest to the goal node is processed first.

A* The path with the smallest path cost + distance to goal is processed first.

Description

This pathfinding example utilizes several technologies

Tiled Map Editor

The Tiled Map Editor is one of the most popular open-source tile map editors available today. It was used to create the tilemap used in this example, which is saved in the tilemaps directory as example_tilemap.tmx. Tiled's native file format, TMX, is a custom XML extension, and as such is both human-readable and easily parsed.

Tiled also supports exporting tilemaps as JSON (JavaScript Object Notation) , which is a very popular serilization format and is almost identical to native JavaScript object declarations. You can see the exported JSON file here: example_tilemap.json. Compare it with the TMX version.

While we could request and parse JSON directly from the server, because we are running this example from the file system, we will convert the JSON tilemap into a JavaScript object declaration. We simply add an assignment: module.exports = to the beginning of the JSON file and resave the file with the .js extension. You can view the resulting JavaScript file here: example_tilemap.js

Browserify

Browserify is a tool for using Node's package manager to bundle JavaScript files into a single bundle to be included in a website. In this example, that bundle is bundle.js and is build from several individual files:

• src/game.js is the primary JavaScript file for the game
• src/tilemap.js is the tilemap engine module
• tilemaps/example_tilemap.js contains a single tilemap's data

Note that both tilemap.js and example_tilemap.js use the module pattern, setting module.exports to a value. In the case of tilemap.js, it is the Tilemap library module. For example_tilemap.js, it is the JavaScript object representing our tilemap data. We require both of these files in game.js, with the lines:
var tilemap = require('./tilemap.js');
var tilemapData = require('../tilemaps/example_tilemap.js');
The require function lets Browserify know that we want the contents of these files to be pulled into this file, and stored as the variables tilemap and tilemapData.

We can ask Browserify to build a single JavaScript file from our source code with the command: > browserify src/game.js > bundle.js This tells browserify to process game.js. When it encounters the require functions, it opens and processes those files, injecting their contents into the JavaScript file it is building, bundle.js, which we can then include as the only JavaScript file in our index.html file. By packaging our code into a single file, we ensure that everything is loaded in the correct order and in a single file, while still keeping our development code in multiple files.

Additionally, Browserify lets us utilize Node packages in our browser JavaScript code (provided we don't use any server-only functions, like file I/O). You can also use Watchify to automatically bundle your changes as you make them.