Choosing non null values from arrays for pathfinding

Hi,

I have been wrestling with this all day and would appreciate help if possible. I have game board set up using a node class that store x and z positon as ints, tiletype, and an isWalkable bool. These are added to a 2d array of nodes . eg nodeArray[xpos,zpos]; The nodes have an iswalkable bool to determine where on the board is walkable and where is not.

I want my non player characters to choose a random direction in any of the valid directions from the current node/position the npc is on whilst avoiding doubling back on itself if there are 2 or more valid directions to travel to.

The thing I am struggling with is choosing a random direction out of the valid ones whilst ignoring the null values. is there a way to do this?

If all the directions are checked and then a count done (using an int numberOfPossDirections to store value) so that Random,Range(0, numberOfPossDirections); can be used it will only return the node with the same index value and not necessarily the right node. The only thing I can think of is to change the value of the random var but this loses some of its randomess.

I originally used lists and had everything working but the I have had a 20 - 30 fps increase since converting to arrays on everything else so and am trying to optimise further. It’s also become a matter of wanting to master a way of doing it old school such as in the days pre List<>.

The Lists just checked all the directions for isWalkable. if a direction was walkable it then added it to a list and then counted the size of the list and did a Random.Range(0, list.count); It then picked out the direction/node stored in the list at that position.

Any help/ideas or alternatives would be greatly appreciated.

Here is a part of the current code in c#.

Thanks

void MoveWander()
{
	movementDirectionInt = 0;
	bool leftH = false;
	bool rightH = false;
	bool upH = false;
	bool downH = false;

	if (currentNode.xPos > 0 && gameboardNPC.NodeArray[currentNode.xPos - 1, currentNode.zPos].isWalkable)
	{
		movementDirectionInt++;
		leftH = true;
	}
	if (currentNode.xPos < gameboardNPC.BoardWidth - 1 && gameboardNPC.NodeArray[currentNode.xPos + 1, currentNode.zPos].isWalkable) 
	{
		movementDirectionInt++;
		rightH = true;
	}
	if (currentNode.zPos < gameboardNPC.BoardHeight - 1 && gameboardNPC.NodeArray[currentNode.xPos, currentNode.zPos + 1].isWalkable) 
	{
		movementDirectionInt++;
		upH = true;
	}
	if (currentNode.zPos > 0 && gameboardNPC.NodeArray[currentNode.xPos, currentNode.zPos - 1].isWalkable) 
	{
		movementDirectionInt++;
		downH = true;
	}

	rnd = Random.Range (0, 4);
	Debug.Log ("random " + rnd);

	if (rnd == 0) {

		if (leftH && previousDirection != MovementDirection.Right) {

			//move left
			this.targetNode = gameboardNPC.NodeArray [currentNode.xPos - 1, currentNode.zPos];
			direction = MovementDirection.Left;
		}
		else rnd++;  // if not valid add 1 and try next
	}
	if (rnd == 1) {

		if (rightH && previousDirection != MovementDirection.Left) {
			//go right
			this.targetNode = gameboardNPC.NodeArray [currentNode.xPos + 1, currentNode.zPos];
			direction = MovementDirection.Right;
		}
		else rnd++; // if not valid add 1 and try next
	}
	if (rnd == 2) {
		if (upH  && previousDirection != MovementDirection.Down) {
			//go up
			this.targetNode = gameboardNPC.NodeArray [currentNode.xPos, currentNode.zPos + 1];
			direction = MovementDirection.Up;
		}
		else rnd++; // if not valid add 1 and try next
	}
	if (rnd == 3) {
		if (downH  && previousDirection != MovementDirection.Up) {
			//go down
			this.targetNode = gameboardNPC.NodeArray [currentNode.xPos, currentNode.zPos - 1];
			direction = MovementDirection.Down;
		}
		else rnd = 0;   //try previous 
	}

	if (movementDirectionInt <= 1) {  // if have to double back 

		if (previousDirection == MovementDirection.Left)
		{
			direction = MovementDirection.Right;
		}
		if (previousDirection == MovementDirection.Right)
		{
			direction = MovementDirection.Left;
		}
		if (previousDirection == MovementDirection.Up)
		{
			direction = MovementDirection.Down;
		}
		if (previousDirection == MovementDirection.Down)
		{
			direction = MovementDirection.Up;
		}
		
		targetNode = previousNode;
	}

It’s quite difficult to put into words so sorry if I am not clear.

You could probably do a similar thing just instead of adding one to rnd try again with a new random (looping the whole section in while loop). Just make sure you test first to see if there are actually any directions (except for backwards) that you can move in (in the top of the code below). Also have like a 1000 cutoff for your random loop just in case you are reaaaally unlucky (beginning of while loop in the code below).

bool solved=false;

if(previousDirection==MovementDirection.right){
if(rightH||upH||downH){
solved=false;
}else{
solved=true;
}
}
else if(previousDirection==MovementDirection.left){
if(leftH||upH||downH){
solved=false;
}else{
solved=true;
}
}
//continue with testing up and down

if(solved==true){//tests to see if backward was the only option
//proceed to turn backward
}

int count=0;

while(solved==false){//the big section

if(count>1000){
break;
}
count++;

rnd=Random.Range(0,3);

if(rnd==0){
if(rightH&&previousDirection!=MovementDirection.left){
//code
solved=true;
}
}

else if(rnd==1){
//dotdotdot, same as above
}

//proceed with the rest of old script and additions

}

Thanks for the reply @Nomenokes and taking the time to write some code out. I was too busy to test this today but I will definitely try this in the next couple of days and let you know how it works.

Really appreciate your help.

doc