Connectable points
[ August 21, 2003 ] by Roberto Valdunciel, alias Rober
A basic algorithm to check if two points are connectable.


Download the source code of this example

This is a simple algorithm that checks if two points A, B are connectable. That is, a character could go from A to B. But just this: it doesn't search a path, and once verified the character moves directly to B without explicit displacement.
We have an array for the MAP, where value 0 indicates a wall, otherwise a walkable position. checkMAP array stores checked positions with 1. Initially it must contain all 0, representing not checked positions.
In my Boxworld version, I actually used tile clips as containers for variables describing walkability and such, and also to store if a position it's checked...

We start checking if end point x1, y1 is walkable. If so, we check its surroundings (up, right, down, left). For each of these positions that's walkable we check its surroundings, while marking as checked (so we don't check after again).
The process finishes in two ways: a whole area it's checked (the process dies with no notice) or we arrive to start point, so the two points are connectable (and we stop remaining processes).
Very innefficient but so simple, for learning purpose.

Use:

//x,y is start position
if(MAP[x1][y1]>0){
  checking = [x,y];
  surround(x1,y1);
}
            

Algorithm:

function surround(x,y){
  check(x,y-1);
  check(x+1,y);
  check(x,y+1);
  check(x-1,y);
}

function check(x,y){
  //stopping remaining processes if necesary
  if(!checking) return;
  //if we arrive to start point x,y
  else if(x == checking[0] && y == checking[1]){
    //stop checking
    checking = null;
    //move character to end point x1,y1 here!
    return;
  }
  //if not yet checked, surround walkable position
  else if(!checkMAP[x][y] and MAP[x][y]>0){
    surround(x,y);
    //mark position as checked
    checkMAP[x][y] = 1;
  }
}


 
 
Name: Roberto Valdunciel, alias Rober
Location: Barcelona, Spain
Age: 26
Flash experience: 2-3 years
Job: University student
Website: http://www14.brinkster.com/boulderflash/
 
 
| 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