A* System For The Grendel Engine

[Meerjel01]

Hello. The Grendel Engine (In A Creation) has had a lot of development done with the first NPC programmed in. Now it should follow a path.

I'm currently stuck in thoughts about my engine's pathfinding which is gonna be an A* system. My plan is to use a connection system for optimization but are stuck on how to implement it. The nodes are scattered around the level and are connected via links to visible and nearby nodes and it creates a path for the NPC to follow from the nearest node (From the NPC) to the point that is nearest the end node. Then when close enough the NPC moves straight to the point (Instead of the end node's own position). This tutorial gave me some insight on it but I need to convert it to use D3DXVECTOR3 coordinates instead.

Anyone has anything to say to help me here? It's needed for now.

 

Meerjel01

[PRince404]

Meerjel, What do you think of Renderware? Wouldn't it be better to just use an existing Engine that was catered for that specific generation?

https://archive.org/details/renderwaregraphics3.7sdkandstudio2.01

https://github.com/Smooth-E/install-renderware

I know you're enjoying making one from scratch but I think you can should make that engine for modern system rather than for an old 6 Gen system.

[Meerjel01]

6 minutes ago, PRince404 said:

Meerjel, What do you think of Renderware? Wouldn't it be better to just use an existing Engine that was catered for that specific generation?

https://archive.org/details/renderwaregraphics3.7sdkandstudio2.01

https://github.com/Smooth-E/install-renderware

I know you're enjoying making one from scratch but I think you can should make that engine for modern system rather than for an old 6 Gen system.

I could use Renderware but I've done a lot of progress on my engine already. I don't know if it'll be a waste if I quit with it. But on other hand I can use it for my Series S games since Unity is dying.

So Renderware works as it should now? Then I can use that.

[PRince404]

25 minutes ago, Meerjel01 said:

I could use Renderware but I've done a lot of progress on my engine already. I don't know if it'll be a waste if I quit with it. But on other hand I can use it for my Series S games since Unity is dying.

So Renderware works as it should now? Then I can use that.

Yeah I that's what I was saying, using your own engine for current Gen, don't quit that project.

I'm still learning programming atm (C++, Python, Lua) so I haven't yet fiddled with this but I believe it should work if it's made to work for those generation system I guess. 

I kind of wanted to demake some 7-8th Gen games for older consoles in the future, so I was thinking this might be the best engine to do it.

[Meerjel01]

But I still need to make an A* pathfinding system like how I described it. Maybe a bit like Half-Life's nodegraph system. Good thing they have it in the SDK.

[corona2222]

3 hours ago, Meerjel01 said:

Anyone has anything to say to help me here? It's needed for now.

Just to clarify what you need help with

"Then when close enough the NPC moves straight to the point (Instead of the end node's own position)."

Is this a problem?

"but I need to convert it to use D3DXVECTOR3 coordinates instead."

Is this what you need help with?

As a general comment on the tutorial, the tutorial author correctly states the issue with dynamic lists / STL and solution of fixed arrays, and also about not needing 3D A* if your 3D game can get away with only using 2D A*, smart. 

[Meerjel01]

Isn't it different on a 3D environment with multiple floors though?

[Meerjel01]

Alright I've finished some code.

struct st_path
{
	int numCorners;
	D3DXVECTOR3* corners;
};

class CAStarNode
{
public:
	int id;
	D3DXVECTOR3 position;
	int numNeighbours;
	CAStarNode* neighbours;
	bool open;
	bool closed;
	CAStarNode* parent;
	
	float gCost, hCost, fCost;

	CAStarNode()
	{
		id = 0;
		gCost = 0;
		hCost = 0;
		fCost = 0;
		open = false;
		closed = false;
		numNeighbours = 0;
	}




};

class CAStarGrid
{
protected:
	IDirect3DDevice8* directDevice;
	CAStarNode* nodes;
	int numNodes;

	D3DXVECTOR3* lines;
	int numLineIndices;
public:

	CAStarGrid()
	{
		directDevice = NULL;
		numNodes = 0;
		numLineIndices = 0;
	}
	
	bool InitGrid(IDirect3DDevice8** device, std::ifstream& file)
	{
		directDevice = *device;

		file >> numNodes;

		nodes = new CAStarNode[numNodes];

		for(int i=0; i < numNodes; i++)
		{
			nodes[i].id = i;
			file >> nodes[i].position.x >> nodes[i].position.y >> nodes[i].position.z;
			
		}

		

		int numConnections = 0;
		
		for(int n=0; n < numNodes; n++)
		{
			file >> numConnections;
			nodes[n].numNeighbours = numConnections;
			nodes[n].neighbours = new CAStarNode[numConnections];
			
			for(int i=0; i < numConnections; i++)
			{
				int nod = 0;
				file >> nod;
				nodes[n].neighbours[i] = nodes[nod];
			}
			
		}
		return true;
	}
	
	bool GetPath(D3DXVECTOR3 start, D3DXVECTOR3 end, st_path& finalPath, float maxStartLimit, float maxEndLimit)
	{
		CAStarNode startNode = GetNearestNode(start);
		if(Distance(startNode.position, start) > maxStartLimit)
			return false;
		CAStarNode endNode = GetNearestNode(end);
		if(Distance(endNode.position, end) > maxEndLimit)
			return false;
		
		for(int n=0; n < numNodes; n++)
		{
			nodes[n].open = false;
			nodes[n].closed = false;
		}
		
		startNode.open = true;
		
		bool found = false;
		while (!found)
		{
			CAStarNode currentNode = startNode;
			
			if(CheckEnd(currentNode.neighbours, currentNode.numNeighbours, endNode))
			{
				endNode.parent = &currentNode;
				found = true;
				break;
			}
			
			currentNode.closed = true;
			
			CAStarNode* neigh = currentNode.neighbours;
			int neighCount = currentNode.numNeighbours;
			
			for(int i=0; i < neighCount; i++)
			{
				if(neigh[i].closed)
				{
					continue;
				} else {
					float gCost = currentNode.gCost + Distance(currentNode.position, neigh[i].position);
					float hCost = Distance(neigh[i].position, endNode.position);
					
					if(!neigh[i].open)
					{
						neigh[i].fCost = hCost + gCost;
						neigh[i].parent = &currentNode;
						
						neigh[i].open = true;
					} else {
						float newFCost = gCost + hCost;
						
						if(neigh[i].fCost > newFCost)
						{
							neigh[i].fCost = newFCost;
							neigh[i].parent = &currentNode;
						}
					}
				}
			}
		}
		
		finalPath = CreatePath(startNode, endNode);
		
		return true;
	}
	
	st_path CreatePath(CAStarNode start, CAStarNode end)
	{
		st_path result;
		result.corners = new D3DXVECTOR3[40];
		
		CAStarNode currentNode = end;
		int current = 0;
		while(currentNode.id != start.id)
		{
			result.corners[current] = currentNode.position;
			
			currentNode = *currentNode.parent;
			current++;
		}
		result.numCorners = current;
		D3DXVECTOR3* temp = new D3DXVECTOR3[current];
		int c = 0;
		for(int i=current - 1; i >= 0; i--)
		{
			temp[i] = result.corners[c];
			c++;
		}
		// std::reverse(result.corners[0], result.corners[current]);
		result.corners = temp;
		delete[] temp;

		return result;
	}
	
	CAStarNode GetNearestNode(D3DXVECTOR3 position)
	{
		CAStarNode result;
		float dist = 1000;
		for(int n=0; n < numNodes; n++)
		{
			float d = Distance(position, nodes[n].position);
			
			if(d < dist)
			{
				result = nodes[n];
				dist = d;
			}
		}
		
		return result;
	}
	
	bool CheckEnd(CAStarNode* neighbours, int numNeighbours, CAStarNode endTarget)
	{
		for(int i=0; i < numNeighbours; i++)
		{
			if(neighbours[i].id = endTarget.id)
				return true;
		}
		return false;
	}
	
};

Gonna improve it later after I've done testing it. Any thoughts?

[corona2222]

6 hours ago, Meerjel01 said:

Isn't it different on a 3D environment with multiple floors though?

I would need to know more about the type of game you're making but a lot of 3D games get away with 2D A*.

[corona2222]

4 hours ago, Meerjel01 said:

Gonna improve it later after I've done testing it. Any thoughts?

from a quick glance looks good. see how it tests 

[Meerjel01]

Tested the code but the result wasn't as expected. I tested it with a small amount of nodes but it should probably work better with more.

[corona2222]

something that helped me understand what was happening to debug and optimize my pathfinding (not A* in my games case) was to render the path points being explored / found in different colours so I could visually see the path, and changed my 'GetPath()' code to be re-entrant so the path is built over a period of time so that I could see the path gradually getting built and the choices it was making and where the (complicated set of rules )code was going wrong. this may help.

[Meerjel01]

1 hour ago, corona2222 said:

something that helped me understand what was happening to debug and optimize my pathfinding (not A* in my games case) was to render the path points being explored / found in different colours so I could visually see the path, and changed my 'GetPath()' code to be re-entrant so the path is built over a period of time so that I could see the path gradually getting built and the choices it was making and where the (complicated set of rules )code was going wrong. this may help.

Thanks for the info. I believe it doesn't work correctly cause of the lack of nodes but I will make a line rendering system for the engine anyway. Also need to make a node-grid file generator somehow.

[Meerjel01]

I have not gotten the program to work yet and tried multiple types of code. Can someone lend a hand here?

[corona2222]

maybe, (when i find a moment) wheres the latest code?

[Meerjel01]

On 1/25/2024 at 2:35 PM, corona2222 said:

maybe, (when i find a moment) wheres the latest code?

Here.

// Init the grid then Get A Path	
bool GetPath(D3DXVECTOR3 start, D3DXVECTOR3 end, st_path& finalPath, float maxStartLimit, float maxEndLimit)
	{
		CAStarNode* startNode = &GetNearestNode(start);
		if(Distance(startNode->position, start) > maxStartLimit)
			return false;
		
		CAStarNode* endNode = &GetNearestNode(end);
		if(Distance(endNode->position, end) > maxEndLimit)
			return false;

	

		CAStarNode* openList = new CAStarNode[numNodes];
		CAStarNode* closedList = new CAStarNode[numNodes];
		

		int currentOpenAmount = 0;
		int currentClosedAmount = 0;


		openList[0] = *startNode;
		currentOpenAmount++;

		while (currentOpenAmount > 0)
		{

			if(currentOpenAmount <= 0)
				break;

			CAStarNode* currentNode = &openList[currentOpenAmount - 1];
			
			int neighCount = currentNode->numNeighbours;
			
			for(int i=0; i < neighCount; i++)
			{
				currentNode->neighbours[i].parent = currentNode;
				currentNode->neighbours[i].gCost = Distance(currentNode->position, currentNode->neighbours[i].position);
				currentNode->neighbours[i].hCost = Distance(currentNode->position, endNode->position);
				currentNode->neighbours[i].fCost = currentNode->neighbours[i].gCost + currentNode->neighbours[i].hCost;
			}
					
			
			
			// CAStarNode* neigh = currentNode->neighbours;
			
			
			
			int ending = 0;
			if(currentNode->id == endNode->id)
			{
				
				CAStarNode* nods = new CAStarNode[numNodes];
				int curNods = 0;
				
				CAStarNode* curNod = currentNode;
				
				bool creating = true;
				while(creating)
				{
					nods[curNods] = *curNod;
					curNods++;
					
					if(curNod->id != startNode->id)
						curNod = curNod->parent;
					else
						creating = false;
				}

				if(curNods <= 0)
					return false;
				
				st_path result;
				result.numCorners = curNods;
				result.corners = new D3DXVECTOR3[curNods];
				for(int n=0; n < curNods; n++)
				{
					result.corners[n] = nods[n].position;
				}
				// finalPath = CreatePath(startNode, endNode);
				finalPath = result;
				
				
				
				
				return true;
			}
			
			
			
			bool picked = false;
			for(int i=0; i < neighCount; i++)
			{
				
				int sel = 0;
				
				
				for(int x=0; x < neighCount; x++)
				{
					
					if(currentNode->neighbours[x].fCost < currentNode->neighbours[sel].fCost)
					{
						sel = x;
					}
				}
				
				if(CheckInClosedList(closedList, currentClosedAmount, currentNode->neighbours[sel]))
				{
					int lar = 0;
					for(int x=0; x < neighCount; x++)
					{
							
						if(currentNode->neighbours[x].fCost > currentNode->neighbours[lar].fCost)
						{
							lar = x;
						}
					}
					
					currentNode->neighbours[sel].fCost = currentNode->neighbours[lar].fCost + 1;
					
					continue;
					/*
					currentNode->neighbours[i].gCost = currentNode->gCost + Distance(currentNode->position, currentNode->neighbours[i].position);
					currentNode->neighbours[i].hCost = Distance(currentNode->neighbours[i].position, endNode->position);
					
					
					currentNode->neighbours[i].fCost = currentNode->neighbours[i].gCost + currentNode->neighbours[i].hCost;
					
					currentNode->neighbours[i].parent = currentNode;
					
					openList[currentOpenAmount] = currentNode->neighbours[i];
					currentOpenAmount++;
					*/
				}
				else
				{
					openList[currentOpenAmount] = currentNode->neighbours[sel];
					currentOpenAmount++;
					picked = true;
					break;
				}
			}
			
			if(picked == false)
			{
				currentOpenAmount--;
			}
			
			closedList[currentClosedAmount] = *currentNode;
			currentClosedAmount++;
			
		}


		
		
		
		return false;
	}
	
	CAStarNode GetNearestNode(D3DXVECTOR3 position)
	{
		CAStarNode result;
		float dist = 1000;
		for(int n=0; n < numNodes; n++)
		{
			float d = Distance(position, nodes[n].position);
			
			if(d < dist)
			{
				result = nodes[n];
				
				dist = d;
			}
		}
		
		return result;
	}

I've just come back to this.

[corona2222]

I'll try find time over the next month

[Meerjel01]

I did some changing to the code and it seems to work a bit better now. But it's not predictable enough and it might be the node grid that I made that is not set up correctly. Gonna make a new graph and changing to other parts of the engine's code to make it easier to work with.

[corona2222]

I've run the code and tried to keep the code to the same as yours as much as possible.

For data I used a fixed node grid (upper range 100 x 100, e.g from 0.0,0.0,0.0 to 99.0, 99.0, 0.0) 

I notice this line is an issue: currentNode->neighbours[i].hCost = Distance(currentNode->position, endNode->position); 

It causes all neighbours to have the same fCost (on a fixed grid), and no 'best' next step forward on the path.

In the tutorial: "H - cost of movement from the current square to the goal...usually an estimate" 
This is likely where the misinterpretation was. The tutorial means "current square" as in the neighbouring square being currently calculated, not the currentNode.

Anyway with the above issue the code results in the final path looking like this:
(Note: the last two columns are not processed by A* because it finds the end node and stops searching)

Visual 1: incorrect path costing

colour key:
light blue = final path (finalPath.corners nodes)
grey = nodes that didn't get examined (never went on the open list or closed list)
green = start node (x = 1.0, y = 1.0, z = 0.0)
Red = end node (x = 98.0, y = 98.0, z = 0.0)

So I changed the neighbouring hCost calc to use the neighbouring square position instead, as follows:

currentNode->neighbours[i].hCost = Distance(currentNode->neighbours[i].position, endNode->position);

Visual 2: corrected path costing

That looks better. 

basically:

gCost is the cost for the entity to travel from its current position to the neighbouring node position. 

hCost is then the cost for the entity to travel from the neighbouring node to the end.

when those two are combined you get fCost which is the result of the entity walking from its current position through the neighbouring node and to the end. 

If we think about what was happening in your code (before that hCost line alteration), the entity walks to the neighbouring node then as if at no cost teleports back to the previous node and walks the rest of the journey from the original node. As all neighbouring nodes cost the same then the code selects the first node as default preference, the first node is whatever node exists first in the neighbour list, this results in all nodes examined until the end node is found (see Visual 1)

It really helps to visualize this stuff 

Edited February 9 by corona2222

[Meerjel01]

Thank you! Didn't know the tutorial had a typo in it.

I tested the code and I think it works better now. But I still think the nodes and their connections are messed up so I'll need to fix those somehow.

[corona2222]

11 hours ago, Meerjel01 said:

Thank you! Didn't know the tutorial had a typo in it.

I tested the code and I think it works better now. But I still think the nodes and their connections are messed up so I'll need to fix those somehow.

fixed_grid_test_data1.txt

my test data, in case it helps. (100x100 nodes)

Let me know if you upload your test code to Gitlab (or similar) might be easier than posting code in this thread. happy to diagnose a little bit (when I have time). 

[Meerjel01]

Made an editor for making node placing and connections files. It's called the Crisp Editor (Cause it's one crispy editor).

It's unfinished but it's doing it's job well. I think.

[Meerjel01]

Current Progress

Has errors unfortunately but it goes somewhere. Also using line/ray casting to detect if the NPC's path is open.

[corona2222]

 

On 3/5/2024 at 12:49 AM, Meerjel01 said:

Made an editor for making node placing and connections files. It's called the Crisp Editor (Cause it's one crispy editor).

Cool. What did you use for the GUI harness / front end?

[Meerjel01]

Have a look.

Crisp Editor