I'm building the very earliest stages of piece movement in a digital board game I'm planning to make.
It's a browser based javascript system.
Basically the players roll to move and need to traverse the arena based on their maximum move distance. However there are floor hazards that damage the player when they are walked on. As the game elapses the arena gets riddled more and more with the hazards until one needs to make risky choices to step over them and take damage.
In the real life version it ultimately just means that you run the piece in the path that you want knowing the amount of steps you're allowed to take. Digitally it's much harder.
I've used A* for the very first time for this and it does the job MOSTLY right. If the path can't be reached without walking through the hazards it will pick the path with the least hazards and mark it's way through which is exactly what I want. However my 'max movement' limiter is very rudimentary... I've taken two approaches:
One was to make it consider tiles that are farther than "move distance" as unpassable and not consider them when continuing the path.
The other was to make the tile resistance value skyrocket to 500 when the steps to the tile exceeds the "move distance".
The first just ends up not being able to find the route occasionally. The second will just make the path even if it is too long simply because it comes to the situation where ALL the possible tiles are 500 + regular resistances, negating the purpose of the huge resistance spike.
In most cases the limiter and the path finding is perfectly functional however I've found one particular instance where it completely fails to find the correct path: If the easiest path is to go AROUND a hazard to get to a tile beside the destination at max moves it will attempt that path for the tile beside it that will drive it into exceeding the move limit.
A couple of examples:
- Purple are the hazards. They ARE passable.
- Blue is the max radius of movement.
- Red outlines are the tiles that the pathfinding has processed to come to the concluded path.
- Pink is the final path.
- Red square is the player.
What I suspect is the problem is that as A* is running through it's list of options it's pushing it's previous steps into the "closed list" thus solidifying it's original assumptions about the path. What happens then is that it takes 4 steps around a square, solidifying the path as it goes, only to hit the max moves before it hits its destination. With no way to re-assess the route it ends up just ending... either by failing to reach the destination via the one type of limiter or by just stepping past the limit anyways.
The Nodes (grid squares) are in a 2D array 10 x 10 called gridList.
The Node Object:
function Node(){
this.element = document.createElement('div');
this.x = 0;
this.y = 0;
this.caltrops = false;
this.passable = true;
this.pathParent = null;
this.g = 0;
this.h = 0;
this.r = 0;
this.f = 9999;
this.element.className = "grid";
this.checkPathValue = function(caller, destination){
var calVal = 0;
var moreThanMove = 0;
if (this.caltrops)
calVal = 25;
/*if (caller.stepsToSource(1) > player.move)
moreThanMove = 500;*/
var r = calVal + moreThanMove;
var g = 10 + caller.g + caller.r;
var h = Math.abs(destination.x-this.x)+Math.abs(destination.y-this.y, 2);
var f = g + h + r;
if (f < this.f){
console.log('Checked pathValue with caller as parent, smaller, updating.');
this.pathParent = caller;
this.r = r;
this.g = g;
this.h = h;
this.f = f;
}
};
this.stepsToSource = function(step){
if (this.pathParent != null){
console.log('Not at source yet, take more steps.');
return this.pathParent.stepsToSource((step+1));
}
else
{
return step;
}
};
}
The Path Finding Script:
//The core pathfinding function for Gladiators movement. Uses A* with a pythagoreum direct line heuristic.
function movementPath(start, end){
var closedList = []; //Begin closedList.
var openList = [start]; //Begin openList. Populate it with the start node.
start.pathParent = null;
console.log('Just before do loop.');
do{
console.log('Just entered do loop.');
//Create current node. Make it's f value impossibly high so it get's replaced
var currentNode = new Node();
currentNode.f = 9999999;
console.log('currentNode.f: '+currentNode.f);
//Set current node to the node with the lowest F value
for (var i in openList)
{
console.log('Inside lowest F loop.');
//if node[i] F is less than or equal to the current node F, replace current node with node[i]
console.log('openList[i].f: '+openList[i].f);
if (openList[i].f < currentNode.f)
{
console.log('Node is smaller than currentNode. Updating.');
currentNode = openList[i];
}
}
$(currentNode.element).addClass("processing");
closedList.push(currentNode); //add current Node to closed list.
//remove current Node from open List.
var index = openList.indexOf(currentNode);
if (index > -1) {
openList.splice(index, 1);
}
console.log('Removed node from openList');
//if we added the destination node to the closed list, we've found the path.
if(closedList.indexOf(end) > -1)
{
console.log('We\'ve found the path!');
break;
}
console.log('Path was not found this loop.');
//Get adjacent nodes
var adjacentNodes = getAdjacentNodes(currentNode);
console.log('Got adjacent nodes.');
//scan through adjacent nodes. If they are already closed, skip. If they are not in the open list, update and add them. Else just update them.
for (var i in adjacentNodes){
if(closedList.indexOf(adjacentNodes[i]) > -1)
{
console.log('Node is in closed list, skip.');
}
else
{
if(openList.indexOf(adjacentNodes[i]) <= -1)
{
console.log('Node is not in open list, adding then updating.');
adjacentNodes[i].checkPathValue(currentNode, end);
openList.push(adjacentNodes[i]);
}
else
{
console.log('Node is in list. Updating.');
adjacentNodes[i].checkPathValue(currentNode, end);
}
}
}
console.log('Finished scanning the Nodes and updating.');
}while(openList.length > 0) // Continue until there is no more available square in the open list (which means there is no path)
}
//Sub function for the pathfinding algorhythm. It checks the adjacent nodes to see if they are passable and returns a list of up to 4 nodes.
function getAdjacentNodes(target){
var x = parseInt(target.x);
var y = parseInt(target.y);
var steps = target.stepsToSource(1);
var list = [];
if(steps <= player.move)
{
var nodeUp = new Node();
nodeUp.passable = false;
var nodeDn = new Node();
nodeDn.passable = false;
var nodeLt = new Node();
nodeLt.passable = false;
var nodeRt = new Node();
nodeRt.passable = false;
if((y-1) > -1){
nodeUp = gridList[y-1][x];
}
if((y+1) < gridList.length){
nodeDn = gridList[y+1][x];
}
if((x-1) > -1){
nodeLt = gridList[y][x-1];
}
if((x+1) < gridList[y].length){
nodeRt = gridList[y][x+1];
}
if (nodeUp.passable && hasClass(nodeUp.element,"moveSpace")){
console.log('nodeUp is passable.');
list.push(nodeUp);
}
if (nodeDn.passable && hasClass(nodeDn.element,"moveSpace")){
console.log('nodeDn is passable.');
list.push(nodeDn);
}
if (nodeLt.passable && hasClass(nodeLt.element,"moveSpace")){
console.log('nodeLt is passable.');
list.push(nodeLt);
}
if (nodeRt.passable && hasClass(nodeRt.element,"moveSpace")){
console.log('nodeRt is passable.');
list.push(nodeRt);
}
}
return list;
}
I've exhausted myself trying to wrap my mind around it, I've only really figured out poor fixes that only sometimes fix the issue and otherwise I just can't find any good keywords online to figure out what I should look into, or how I should approach fixing this.
Any help is greatly appreciated.
