• Advertisement

Algorithm Navigation Mesh Generation

Recommended Posts

I am currently attempting to make a navigation mesh for our 2D top down game, which is a multiplayer game using Node.js as the server communication. At the moment, I have implemented A* over an obstacle hardnessmap, which is awfully slow and laggy at times when we test our game on Heroku. I have been trying to find an algorithm to automatically generate the navmesh after map creation, instead of me having to do this manually. I am currently attempting to use Delaunay's Triangulation Divide and Conquer algorithm, but I am running into some issues. I have already asked a question on StackOverflow and am not getting many suggestions and help from it, so I figured I would come here. Is there another algorithm that might be better to use for the navmesh generation in comparison to Deluanay's Triangulation? My current implementation seems extremely buggy during the merge step and I cannot find the error. I have checked over the code countless times, comparing it to the description of the algorithm from http://www.geom.uiuc.edu/~samuelp/del_project.html

My current code is this:

class MapNode
{
	constructor(x, y)
	{
		this.position = new Vector(x, y);
		this.neighbors = [];
	}

	distance(n)
	{
		return this.position.distance(n.position);
	}

	inNeighbor(n)
	{
		for (let i = 0; i < this.neighbors.length; i++)
		{
			if (this.neighbors[i] === n)
				return true;
		}

		return false;
	}

	addNeighbor(n)
	{
		this.neighbors = this.neighbors.filter((node) => node != n);
		this.neighbors.push(n);
	}

	addNeighbors(arr)
	{
		let self = this;
		arr.forEach((n) => self.neighbors.push(n));
	}

	removeNeighbor(n)
	{
		this.neighbors = this.neighbors.filter((neighbor) => neighbor != n);
	}
}

class Triangle
{
	constructor(p1, p2, p3)
	{
		this.p1 = p1;
		this.p2 = p2;
		this.p3 = p3;

		this.neighbors = [];
	}

	addNeighbors(n)
	{
		this.neighbors.push(n);
	}
}

function genSubMat(matrix, ignoreCol)
{
	let r = [];
	for (let i = 0; i < matrix.length - 1; i++)
	{
		r.push([]);
		for (let j = 0; j < matrix[0].length; j++)
		{
			if (j != ignoreCol)
				r[i].push(matrix[i + 1][j]);
		}
	}

	return r;
}

function determinantSqMat(matrix)
{
	if (matrix.length != matrix[0].length) return false;

	if (matrix.length === 2) return matrix[0][0] * matrix[1][1] - matrix[1][0] * matrix[0][1];

	let det = 0;
	for (let i = 0; i < matrix.length; i++)
	{
		let r = genSubMat(matrix, i);
		let tmp = matrix[0][i] * determinantSqMat(r);
		if (i % 2 == 0)
			det += tmp;
		else
			det -= tmp;
	}

	return -det;
}

// if d is in the circle formed by points a, b, and c, return > 0
// d is on circle, return 0
// d is outside of circle, return < 0
function inCircle(a, b, c, d)
{
	let arr = [a, b, c, d];
	let mat = [
		[],
		[],
		[],
		[]
	];

	for (let i = 0; i < arr.length; i++)
	{
		mat[i][0] = 1;
		mat[i][1] = arr[i].position.x;
		mat[i][2] = arr[i].position.y;
		mat[i][3] = arr[i].position.x * arr[i].position.x + arr[i].position.y * arr[i].position.y;
	}
	return determinantSqMat(mat);
}

function walkable(from, to, hardnessMap)
{
	let diff = new Vector(to.x - from.x, to.y - from.y);
	if (Math.abs(diff.x) > Math.abs(diff.y)) diff.scale(Math.abs(1 / diff.x));
	else diff.scale(Math.abs(1 / diff.y));
	let current = new Vector(from.x + diff.x, from.y + diff.y);
	while (Math.round(current.x) != to.x || Math.round(current.y) != to.y)
	{
		if (hardnessMap[Math.floor(current.y)][Math.floor(current.x)] === 1)
			return false;
		current.x += diff.x;
		current.y += diff.y;
	}

	return true;
}

function getLowest(nodes)
{
	let lowest = nodes[0];
	for (let i = 1; i < nodes.length; i++)
	{
		if (nodes[i].position.y < lowest.position.y)
			lowest = nodes[i];
	}

	return lowest;
}

// returns the angle between 2 vectors, if cw is true, then return clockwise angle between,
// else return the ccw angle between. b is the "hinge" point
function angleBetween(a, b, c, cw)
{
	let ba = new Vector(a.position.x - b.position.x, a.position.y - b.position.y);
	let bc = new Vector(c.position.x - b.position.x, c.position.y - b.position.y);
	let v0 = new Vector(0, 1);

	let angleBA = v0.angleBetween(ba) * 180 / Math.PI;
	if (angleBA < 0) angleBA += 360;
	let angleBC = v0.angleBetween(bc) * 180 / Math.PI;
	if (angleBC < 0) angleBC += 360;

	let smallest = Math.min(angleBA, angleBC);
	let largest = Math.max(angleBA, angleBC);

	let angle = largest - smallest;

	return (cw) ? angle : 360 - angle;
}

function sortSmallestAngle(a, b, list, cw)
{
	list.sort((m, n) =>
	{
		let vab = new Vector(a.position.x - b.position.x, a.position.y - b.position.y);
		let vmb = new Vector(m.position.x - b.position.x, m.position.y - b.position.y);
		let vnb = new Vector(n.position.x - b.position.x, n.position.y - b.position.y);

		if (cw)
			return vab.angleBetween(vmb, cw) - vab.angleBetween(vnb, cw);
		else
			return vab.angleBetween(vnb, cw) - vab.angleBetween(vmb, cw);
	});
}

// a is in list, b is in the other list
function getPotential(a, b, list, cw)
{
	sortSmallestAngle(b, a, list, cw);
	for (let i = 0; i < list.length - 1; i++)
	{
		let angle = angleBetween(b, a, list[i], cw);
		if (angle > 180) return false;
		else if (inCircle(a, b, list[i], list[i + 1]) <= 0)
			return list[i];
		else
		{
			a.removeNeighbor(list[i]);
			list[i].removeNeighbor(a);
		}
	}

	let potential = list[list.length - 1];
	if (potential)
	{
		let angle = angleBetween(a, b, potential, cw);
		if (angle > 180) return false;
		return potential;
	}
	return false;
}

function merge(leftNodes, rightNodes, leftBase, rightBase, hardnessMap)
{
	leftBase.addNeighbor(rightBase);
	rightBase.addNeighbor(leftBase);

	let newLeft = leftNodes.filter((n) => n != leftBase);
	let newRight = rightNodes.filter((n) => n != rightBase);

	let potentialLeft = getPotential(leftBase, rightBase, newLeft, false);
	let potentialRight = getPotential(rightBase, leftBase, newRight, true);

	if (!potentialLeft && !potentialRight) return;
	else if (potentialLeft && !potentialRight)
		merge(newLeft, newRight, potentialLeft, rightBase, hardnessMap);
	else if (potentialRight && !potentialLeft)
		merge(newLeft, newRight, leftBase, potentialRight, hardnessMap);
	else
	{
		if (inCircle(leftBase, rightBase, potentialLeft, potentialRight) <= 0)
			merge(newLeft, newRight, potentialLeft, rightBase, hardnessMap);
		if (inCircle(leftBase, rightBase, potentialRight, potentialLeft) <= 0)
			merge(newLeft, newRight, leftBase, potentialRight, hardnessMap);
	}
}

// divide and conquer algorithm
function delaunay(nodes, hardnessMap)
{
	if (nodes.length <= 3)
	{
		for (let i = 0; i < nodes.length; i++)
			for (let j = 0; j < nodes.length; j++)
				if (i != j)
					nodes[i].addNeighbor(nodes[j]);

		return nodes;
	}
	else
	{
		nodes.sort((a, b) =>
		{
			let tmp = a.position.x - b.position.x;
			if (tmp === 0) return b.position.y - a.position.y;
			return tmp;
		});

		let l = nodes.length;

		let leftNodes;
		let rightNodes;

		if (l === 4)
		{
			leftNodes = delaunay(nodes.slice(0, 3), hardnessMap);
			rightNodes = delaunay(nodes.slice(3, 4), hardnessMap);
		}
		else
		{
			leftNodes = delaunay(nodes.slice(0, Math.floor(nodes.length / 2)), hardnessMap);
			rightNodes = delaunay(nodes.slice(Math.floor(nodes.length / 2), nodes.length), hardnessMap);
		}
		let leftBase = getLowest(leftNodes);
		let rightBase = getLowest(rightNodes);

		merge(leftNodes, rightNodes, leftBase, rightBase, hardnessMap);

		console.log("=============================MergeComplete================================");
		return nodes;
	}
}

 

Share this post


Link to post
Share on other sites
Advertisement

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now


  • Advertisement
  • Advertisement
  • Popular Tags

  • Advertisement
  • Popular Now

  • Similar Content

    • By Allagia X
      An original fantasy RP game needs dedicated, self-motivated, and chill individuals! We have a story and general plot already set up, ready to be expanded upon. 

      Miasma: Twilight Decree is a 2D roleplay adventure game. It’s set in a unique fantasy world with a vast map containing continents and oceans alike. Players are given one objective: to endure the troublous environments Allagia have to offer and successfully progress through time to reach the Age of Technology. The stakes are high, and every character’s actions can alter the world – or reset everything back to the beginning ages. MTD features a blend of survival aspects, dark themes, with the ability to make a mark in the history books.

      What we're currently looking for:
       
      • Writers - Super creative individuals who have experience in lore-making, world-building, and know their way around fantasy writing. All of the general elements are here [setting, plot, etc.] and need some "fluffing out"[quest lines, clans/ factions/ families, etc.]. Bonus points to those who can whip up spells and skills.
      • Artists - Mainly those who specialize in pixelated art, or people who can make concept art [since we lack pictures]. 
      • Project Manager - Someone who is organized and can keep this project on the rails. As thorough as I am, it's difficult to cover all the bases on my own. 
      • Other Positions - Anything else to fill in the gaps. We currently use Wikidot for our wiki; someone with CSS and syntax experience to polish it up would be awesome. A musician/ composer for all things musical. Way later down the road, we'll need community managers, DMs, and the such, though it isn't necessary at the moment. 

      Other information:

      I've been working on this project since the beginning of 2017 with a group of friends. Life basically prohibited a lot of us from continuing on with it, and it went on hiatus for a while. I'm making an attempt to bring this back from the dead since plenty of time and effort went into it beforehand. It goes without saying that I also have a passion for roleplaying. 

      I cannot stress enough that anyone interested should be into fantasy settings or D&D. Otherwise, you're probably not going to have fun with helping!

      We do have a Patreon with a few supporters, and Discord. Until things really start moving, we'll be using Discord to collaborate. 

      For any questions, comments, or concerns, feel free to comment below or add me on discord @ Allagia X#9174 [best method of contact] for more info about this project.
    • By francoisdiy
      So I wrote a programming language called C-Lesh to program games for my game maker Platformisis. It is a scripting language which tiles into the JavaScript game engine via a memory mapper using memory mapped I/O. Currently, I am porting the language as a standalone interpreter to be able to run on the PC and possibly other devices excluding the phone. The interpreter is being written in C++ so for those of you who are C++ fans you can see the different components implemented. Some background of the language and how to program in C-Lesh can be found here:

      http://www.codeloader.net/readme.html
      As I program this thing I will post code from different components and explain.
    • By Manuel Berger
      Hello fellow devs!
      Once again I started working on an 2D adventure game and right now I'm doing the character-movement/animation. I'm not a big math guy and I was happy about my solution, but soon I realized that it's flawed.
      My player has 5 walking-animations, mirrored for the left side: up, upright, right, downright, down. With the atan2 function I get the angle between player and destination. To get an index from 0 to 4, I divide PI by 5 and see how many times it goes into the player-destination angle.

      In Pseudo-Code:
      angle = atan2(destination.x - player.x, destination.y - player.y) //swapped y and x to get mirrored angle around the y axis
      index = (int) (angle / (PI / 5));
      PlayAnimation(index); //0 = up, 1 = up_right, 2 = right, 3 = down_right, 4 = down

      Besides the fact that when angle is equal to PI it produces an index of 5, this works like a charm. Or at least I thought so at first. When I tested it, I realized that the up and down animation is playing more often than the others, which is pretty logical, since they have double the angle.

      What I'm trying to achieve is something like this, but with equal angles, so that up and down has the same range as all other directions.

      I can't get my head around it. Any suggestions? Is the whole approach doomed?

      Thank you in advance for any input!
       
    • By isu diss
      I'm trying to duplicate vertices using std::map to be used in a vertex buffer. I don't get the correct index buffer(myInds) or vertex buffer(myVerts). I can get the index array from FBX but it differs from what I get in the following std::map code. Any help is much appreciated.
      struct FBXVTX { XMFLOAT3 Position; XMFLOAT2 TextureCoord; XMFLOAT3 Normal; }; std::map< FBXVTX, int > myVertsMap; std::vector<FBXVTX> myVerts; std::vector<int> myInds; HRESULT FBXLoader::Open(HWND hWnd, char* Filename, bool UsePositionOnly) { HRESULT hr = S_OK; if (FBXM) { FBXIOS = FbxIOSettings::Create(FBXM, IOSROOT); FBXM->SetIOSettings(FBXIOS); FBXI = FbxImporter::Create(FBXM, ""); if (!(FBXI->Initialize(Filename, -1, FBXIOS))) { hr = E_FAIL; MessageBox(hWnd, (wchar_t*)FBXI->GetStatus().GetErrorString(), TEXT("ALM"), MB_OK); } FBXS = FbxScene::Create(FBXM, "REALMS"); if (!FBXS) { hr = E_FAIL; MessageBox(hWnd, TEXT("Failed to create the scene"), TEXT("ALM"), MB_OK); } if (!(FBXI->Import(FBXS))) { hr = E_FAIL; MessageBox(hWnd, TEXT("Failed to import fbx file content into the scene"), TEXT("ALM"), MB_OK); } FbxAxisSystem OurAxisSystem = FbxAxisSystem::DirectX; FbxAxisSystem SceneAxisSystem = FBXS->GetGlobalSettings().GetAxisSystem(); if(SceneAxisSystem != OurAxisSystem) { FbxAxisSystem::DirectX.ConvertScene(FBXS); } FbxSystemUnit SceneSystemUnit = FBXS->GetGlobalSettings().GetSystemUnit(); if( SceneSystemUnit.GetScaleFactor() != 1.0 ) { FbxSystemUnit::cm.ConvertScene( FBXS ); } if (FBXI) FBXI->Destroy(); FbxNode* MainNode = FBXS->GetRootNode(); int NumKids = MainNode->GetChildCount(); FbxNode* ChildNode = NULL; for (int i=0; i<NumKids; i++) { ChildNode = MainNode->GetChild(i); FbxNodeAttribute* NodeAttribute = ChildNode->GetNodeAttribute(); if (NodeAttribute->GetAttributeType() == FbxNodeAttribute::eMesh) { FbxMesh* Mesh = ChildNode->GetMesh(); if (UsePositionOnly) { NumVertices = Mesh->GetControlPointsCount();//number of vertices MyV = new XMFLOAT3[NumVertices]; for (DWORD j = 0; j < NumVertices; j++) { FbxVector4 Vertex = Mesh->GetControlPointAt(j);//Gets the control point at the specified index. MyV[j] = XMFLOAT3((float)Vertex.mData[0], (float)Vertex.mData[1], (float)Vertex.mData[2]); } NumIndices = Mesh->GetPolygonVertexCount();//number of indices MyI = (DWORD*)Mesh->GetPolygonVertices();//index array } else { FbxLayerElementArrayTemplate<FbxVector2>* uvVertices = NULL; Mesh->GetTextureUV(&uvVertices); int idx = 0; for (int i = 0; i < Mesh->GetPolygonCount(); i++)//polygon(=mostly triangle) count { for (int j = 0; j < Mesh->GetPolygonSize(i); j++)//retrieves number of vertices in a polygon { FBXVTX myVert; int p_index = 3*i+j; int t_index = Mesh->GetTextureUVIndex(i, j); FbxVector4 Vertex = Mesh->GetControlPointAt(p_index);//Gets the control point at the specified index. myVert.Position = XMFLOAT3((float)Vertex.mData[0], (float)Vertex.mData[1], (float)Vertex.mData[2]); FbxVector4 Normal; Mesh->GetPolygonVertexNormal(i, j, Normal); myVert.Normal = XMFLOAT3((float)Normal.mData[0], (float)Normal.mData[1], (float)Normal.mData[2]); FbxVector2 uv = uvVertices->GetAt(t_index); myVert.TextureCoord = XMFLOAT2((float)uv.mData[0], (float)uv.mData[1]); if ( myVertsMap.find( myVert ) != myVertsMap.end() ) myInds.push_back( myVertsMap[ myVert ]); else { myVertsMap.insert( std::pair<FBXVTX, int> (myVert, idx ) ); myVerts.push_back(myVert); myInds.push_back(idx); idx++; } } } } } } } else { hr = E_FAIL; MessageBox(hWnd, TEXT("Failed to create the FBX Manager"), TEXT("ALM"), MB_OK); } return hr; } bool operator < ( const FBXVTX &lValue, const FBXVTX &rValue) { if (lValue.Position.x != rValue.Position.x) return(lValue.Position.x < rValue.Position.x); if (lValue.Position.y != rValue.Position.y) return(lValue.Position.y < rValue.Position.y); if (lValue.Position.z != rValue.Position.z) return(lValue.Position.z < rValue.Position.z); if (lValue.TextureCoord.x != rValue.TextureCoord.x) return(lValue.TextureCoord.x < rValue.TextureCoord.x); if (lValue.TextureCoord.y != rValue.TextureCoord.y) return(lValue.TextureCoord.y < rValue.TextureCoord.y); if (lValue.Normal.x != rValue.Normal.x) return(lValue.Normal.x < rValue.Normal.x); if (lValue.Normal.y != rValue.Normal.y) return(lValue.Normal.y < rValue.Normal.y); return(lValue.Normal.z < rValue.Normal.z); }  
    • By Terry Jin
      Hi everyone! 

      I am from an indie studio that has received funding for our concept and is ready to create the next generation 2D Pokemon-inspired MMORPG called Phantasy World. This ad is for a volunteer position but hopefully will transition into something more. Our vision is to create a game that draws inspiration from the series but is dramatically different in both aesthetics and gameplay as the work would be our own.
       
      We are hoping that you can help us make this a reality and are looking for game developers familiar with the unreal engine and would be happy to work on a 2D top down game. Sprite artists are also welcome as we are in desperate need of talented artists! Join our discord and let's have a chat! https://discord.gg/hfDxwDX

      Here's some of our in game sprites for playable characters while moving around the game world! Hope to see you soon!
       


  • Advertisement