Tonypa's tile-based tutorials (updated)
[ September 03, 2004 ] by Tonu Paldra, alias Tonypa
A long, well organized and in depth series of articles that cover all the aspects of tile-based games: moving, jumping, scrolling, shooting and much more!


Intro
Why tiles?
Map format
More maps
Creating tiles
The hero
Keys to move
Hit the wall
Open the door
Jumping
Clouds
Ladders
Stupid enemy
More on enemy
Shoot him
Getting items
Moving tiles
Scrolling
More scrolling
Depth
Isometric view
Mouse to move
Isometric mouse
Isometric scroll
Rotate hero
Rotate bground
Pathfinding
More pathfinding
Slopes

MORE PATHFINDING

The breath-first search we created in last chapter, is not too fast. Thats why this time we look into faster algorithm, that would allow usage of larger maps without slowing down the game:


BEST-FIRST

You may remember from the last chapter, how breath-first search expanded all the nodes in every direction. It had no idea, where the target was, it looked everywhere. Thats why it took forever to find the path. It did find shortest path every time, but lets be honest, whats more important, finding perfect path or making playable game?

So, lets introduce best-first search. This time we will try to see how far the target is from current node and we attach the estimated distance with each node.

cost = Math.abs(x - targetx) + Math.abs(y - targety);

We count how many steps is target from the current tile both in x and y direction and add steps from both directions.

The other difference is, that we keep our Unchecked_Neighbours array sorted from the node with lowest cost to the target (it should be near the target) to the node with highest cost. By sorting the array we always look into the direction of the target, before going in other directions. But be warned, while the best-first search always finds the path, its not always the shortest path. Its still much faster in most maps then A*.


BEST-CODES

Take code from previous chapter and change the findPath function. We need to add cost to the first node:

var cost = Math.abs(startx - targetx) + Math.abs(starty - targety);
path[path.name] = {x:startx, y:starty, visited:true,
	parentx:null, parenty:null, cost:cost};

and we have to pass the target to the addNode function:

addNode (N, N.x + 1, N.y, targetx, targety);
addNode (N, N.x - 1, N.y, targetx, targety);
addNode (N, N.x, N.y + 1, targetx, targety);
addNode (N, N.x, N.y - 1, targetx, targety);

In the addNode function remember, that target is passed to it too:

function addNode (ob, x, y, targetx, targety)
{
  path.name = "node_" + y + "_" + x;
  if(game["t_" + y + "_" + x].walkable)
  {
    var cost = Math.abs(x - targetx) + Math.abs(y - targety);
    if (path[path.name].cost > cost or path[path.name].cost == undefined)
    {
      path[path.name] = {x:x, y:y, visited:false, parentx:ob.x, parenty:ob.y, cost:cost};
      for(var i=0; i<path.Unchecked_Neighbours.length; i++)
      {
        if (cost < path.Unchecked_Neighbours[i].cost)
        {
          path.Unchecked_Neighbours.splice(i, 0, path[path.name]);
          break;
        }
      }
      if (i >= path.Unchecked_Neighbours.length)
      {
        path.Unchecked_Neighbours[path.Unchecked_Neighbours.length] = path[path.name];
      }
    }
  }
}

Cost is calculated same way. Then we check if the node is already created or if it is created, but has currently higher cost.

After making new node we start to loop through the Unchecked_Neighbours array and compare cost of current node with cost of each element in the array. We break the loop, if we have found node in the array, that has higher cost. We insert new node in that spot into array.

Last if statement checks if we have looped through entire array without finding any node with higher cost. That means we add our new node in the end of the array.


FASTER, FASTER

If the pathfinding still takes too long, because you have large maps, you might consider precalculating some parts of the maps or using waypoints to lead char from one part of the map into another part without looking through all the tiles.

Michael Grundvig has created extremely fast pathfinding system using precalculated paths. You can read about it here. He calculates all the paths from each tile to every tile and stores those paths with the maps. When char wants to go from one tile to another during the game, he only has to pick the path and walk.

Waypoints system would slice the map virtually up into smaller maps, connected with prededefined paths. Then you would need to find only which minimap starting tile and target tile belong and use memorised path to get from starting minimap to target. That allows paths for really-really big maps too.

Another way for calculation of larger paths without slowing down the game would be spreading the path calculation over several frames. You would need to break the pathfinding loop after certain steps, remember the current state, then run other code in the game and in the next frame continue finding the path. Andre Michelle has posted very nice example of this idea here.

You can download the source fla with all the code and movie set up here.


     
 
 
Name: Tonu Paldra, alias Tonypa
Location: Estonia
Age: 34
Flash experience: Discovered Flash4 in the year 2000 and fell in love with it. Abandoned Flash4, when they ended Flash4 help forum in Flashkit. Been playing with Flash only in spare time, thinking its great hobby
Job: Magazine designer
Website: http://www.tonypa.pri.ee/
 
 
| Homepage | News | Games | Articles | Multiplayer Central | Reviews | Spotlight | Forums | Info | Links | Contact us | Advertise | Credits |

| www.smartfoxserver.com | www.gotoandplay.biz | www.openspace-engine.com |

gotoAndPlay() v 3.0.0 -- (c)2003-2008 gotoAndPlay() Team -- P.IVA 03121770048