Dead-End Locator

Gamer86 · February 4, 2015, 12:31pm

Hi guys & gals,

I’m working on a concept that requires finding all dead ends in a procedurally generated tile-based maze environment. I’ve successfully integrated the pathfinding into the project using the “grid” graph-type.

The players is able to directly select rendered representation of the paths that branch out from their current location to places of interest such as doors and other interactive elements scattered throughout the maze, with the character setting off on the path!

The problem I have is in trying to support “wrong-turns” as movement options, i.e. a path choice might lead from the players location to a ‘dead-end’. Due to the random nature of the maze creation I cannot mark these locations in advanced in editor. I had hoped to derive a method (maybe using the FloodPath pathfinder) to locate these positions, but am not sure where to start. My initial thoughts are as follows:

Finding Dead Ends:

Access grid graph directly and manually flood
On each step if I reach a node with no open neighbours -> round the position of node to nearest “tile-center” -> if this tile isn’t in the list of “dead-ends” - >add it to “dead-ends” list.

I expect to then try and path to all genuine areas of interest (doors, etc.) and these dead-ends, rendering the set of direction choices to the player.

I’m not certain how I can directly access the grid-graph node to perform a per-node operation on them to achieve this ‘dead-end’ finder system. If anyone has any light they could shed on this idea. Am I going the long way round? Can this be accomplished with in-built functionality in the current A* project release?

Thanks for reading and look forward to any bright ideas anyone has on this topic!

aron_granberg · February 4, 2015, 12:36pm

Hi

On a grid graph it is a bit tricky to exactly define ‘dead end’.
Corridors in grid graphs are usually wider than a single node (or is this not the case in your game?). So for example it would be possible for a path to start in one end of a corridor, move to the other end and then go back while not crossing the same nodes, so even though a human might classify it as a dead end, it’s not a dead end in the technical sense.

The problem with just flooding is that the flooding might find all kinds of places which it classifies as dead ends. For example it might find that the corner of a room is a dead end.

Could you show a screenshot of how your game looks (with the graph visible), then I might be able to help more.

aron_granberg · February 4, 2015, 12:40pm

A good algorithm to do this “properly” would probably be the watershed algorithm
then build up a graph of the segmented regions and run an algorithm to repeatedly remove all 1-connected nodes from it and classify those as dead ends.
Might calculate incorrect if corridors in the game contain objects in the middle of them such as pillars or boxes however.

It is a bit tedious to implement though…

Gamer86 · February 4, 2015, 11:07pm

Thanks for getting in touch so quickly Aron!

Below is a raw visual of an example situation in which i’ve mark some locations I’d like to be able to determine as dead-ends.

I wonder if you’d recommend using another graph type altogether to allow for an easier analysis?

I have assessed your idea about watershed and I can see its merits - and agree about the potentially tedious implementation you mentioned.

I have avoided changing the node-width in the AstarPath component when generating graphs as i’m quite content with the density which it is currently generating as it will allow for a non-uniform corridor width which I intend to support.

A feature of the procedural level generation is that it IS strictly tile based - so I’ve been thinking it should be possible to quantise the grid nodes generated by your project such that all nodes with a position within a single tile area are ‘collated’.

I’ve made some progress with this and am pleased with the initial results… however I’ve hit a snag which I hoped you could shed some light on.

Below is a snap shot of the progress to date:

Cyan Dots: Center of QuantizedNode instances created
Magenta Dots: NavGraph::Nodes[] which belong to QuantizedNode

What i’ve done here is execute a FindDeadEnds method that creates a List<>. I invoke this in response by subscribing to AstarPath delegates:

-OnLatePostScan
-OnGraphsUpdated

Assumption: I am assuming all Node::connections are populated at this point! Is this Wrong?

The QuantizedNodes class used looks as follows:


`
	public class QuantizedNode
	{
		//center of the grid tile the nodes belong to
		public readonly Vector3 searchCenter;

		//quantizedNodeIndex - ref for remapping node connections to QuantizedNode connections
		public readonly int nodeIndex;

		//object that represents this node in world space
		public GameObject markerObject;

		//list of NavGraph::nodes that are stored and used to create the QuantizedNode with useable connections
		public List<Node> nodes = new List<Node>();

		//a list of the other quantized nodes to which this one is connected
		public List<QuantizedNode> connections = new List<QuantizedNode>();

		//adds a connected QuantizedNode to be connected to this one
		public void AddConnection(QuantizedNode qn)
		{
			//dont add connections to self!
			if(qn == this) return;

			connections.Add(qn);
		}

		//ctor
		public QuantizedNode(int nodeIndex, Vector3 searchCenter)
		{
			//cache node index
			this.nodeIndex = nodeIndex;
			//cache center of area 
			this.searchCenter = searchCenter;
		}

		//returns the centeral position of the walkable nodes that belong to this QuantizedNode
		public Vector3 walkableCenter
		{
			get
			{
				Vector3 vec = Vector3.zero;

				for(int i = 0; i < nodes.Count; i++)
					vec += (Vector3)nodes[i].position;

				vec /= nodes.Count;

				return vec;
			}
		}
	}
`

The logic for the method that builds and processes graph::nodes to build the List<> follows - however it is failing as every Node being processed has a null connections array at the time of being processed.

`
//for every walkable node in graph.nodes
↳//round nodes position to nearest tile center
   //assign node to instance of QuantizedNode::nodes[] based of rounded pos
   //also add entry to temp Dictionary<Node, int> to lookup a nodes parent for quick redirect when building QuantizedNode connections based of its nodes

//process each QuantizedNode to build its connections to other QuantizedNodes based on the connections of the Nodes it contains

//foreach QuantizedNode in quantizedNodesList
↳//foreach Node in QuantizedNode::nodes
    ↳//if node hasn't any connections (node::connections==null OR ::Length==0
        ↳//node::UpdateConnections
	 **↳//if node STILL no connections -> process next node in QuantizedNode::nodes
		
(** = always failing here!)
			
   //if node was found to have connections
   ↳//foreach node in node::connections
	↳//if the node ins't walkable -> skip process next node in node::connections
	   ↳//if there is a QuantizedNode lookup value for the Node being processed
	      //get the connectionIndex (QuantizedNode::nodeIndex) that contains this Node
	      //add the QuantizedNode with QuantizedNode::nodeIndex == connectionIndex to QuantizedNode being processed
`

As the image shows the process is working pretty well. There are issues present due to my test world layout not strictly adhering to the tile sizes i’m passing to the system. However clearly the Node::connections haven’t been constructed at this time after AstarPath::OnLatePostScan & AstarPath::OnGraphsUpdated.

Could you please let me know what I might be doing wrong here?

Many Thanks Aron.

Gamer86 · February 4, 2015, 11:12pm

I know that was a hell of a long post but wanted to follow up with a mention that I’m aware that all centers are being displayed and not just the ‘dead-ends’.

I intend to easily identify these after by finding QuantizedNodes with only 1 connection. Obviously I can only remap these connections between QuantizedNodes properly once i’ve access to properly initialized Nodes in the Graph. Why might the Node::connections still be null at this point?

Look forward to your thoughts.

aron_granberg · February 5, 2015, 8:39am

Hi

OK. That approach could definitely work. You might miss some cases, but it should mostly work.
It seems I have failed to update some documentation since I moved some fields around (previously there was a nice explanation for this in the docs). The connections array is not set normally for grid nodes, connections are stored in a bit mask for performance reasons. Use the GetConnections methods to iterate through all of them.

Gamer86 · February 5, 2015, 9:34am

Ahh interesting. I must apologise… it is clearly stated in the comment on the graph::Nodes accessor that the GridGraph stores this differently!

I’ve reviewed the source and see how you’re bit-shifting the connection status which is helpful for me simplifying zero connection checks using GridNode::HasAnyGridConnections.

I am still a little confused as how i get access to the GridNodes that are the actual neighbours of a given GridNode. Should I modify a version of GridGraph::CheckConnections to return these references or does a means to get these nodes already exist?

Cheers once again Aron.

Gamer86 · February 5, 2015, 10:06am

OK i see how this works now.

`
if (node.GetConnection (i)) 
{
	GridNode other = nodes[node.GetIndex ()+neighbourOffsets[i]] as GridNode;
}
`

Had though I’d have found a Method for accessing this with a cardinal argument!

Will just create my own convenience method instead.

Cheers!