sheep19

I have to implement path finding on GPU as a university project. I am going to use A* (I have used it before for solving 8-puzzles)

 

However, I can't think of a way to make it efficient for a single agent. I probably have to simulate multiple agents to get reasonable performance speed-up.

I read somewhere that I should spawn a thread for each agent, which seems reasonable.

 

However, how would the agents avoid each other? The world (2D map) would have to be updated each time one moves (this means that I must have a "central" array where the changes will be written to, which will make performance suffer on a GPU (or not?)). I know this is an AI forum, so the question I am asking is, how can I update each agents position with the least number of updates?

Hello,

I am an aspiring game programmer. Currently I am in my 3rd year (of 4) of studies (Computer Science).

I am writing this topic to get some advice about a 3D game I will develop that will help me get a job in the industry.

Experience:
I am experienced with the following programming languages:
1) C++ -- developed 3 2D games
2) C# -- developed 1 2D game (using XNA)
3) Java -- developed 1 2D game (on android)
4) D -- developed a ray tracer (which is fairly limited at this time).

The games can be found here:
http://greenbits.webs.com/games.htm

Here is a picture of the raytracer:
 http://i46.tinypic.com/2cwn3wx.png

The future:
During the last week I decided to make a 3D game to use for getting a job in the industry. As I understand, it is a requirement to have a 3D game in my portfolio (please correct me if I am wrong).

So I was thinking of a stealth game that will be 3D, with physics and good AI.
Story: The story is short. The hero gets abducted and must escape the place where he has awoken at (a forest maybe).

It will feature a top down camera, like league of legends (similarities stop here).

Here is a prototype picture I painted.


The player starts at the lower left corner and must reach the top right one.
In the middle of the stage there is an enemy who is partolling the area.
* The player cannot attack/kill anyone.
* If the player steps into the "view radius" of an enemy, he will be spotted. The enemy will run towards the player and kill him. So the player must not get spotted.
* When the player walks, he is making noise. If the noise circle (sphere in the game) of the player intersects with the hearing circle of an enemy, the enemy will get in "alert" state. He will walk towards the position where the noise came from and try to find who did it.

There will be certain things the player can use to make it to his destination:
* A device that will make lots of noise to attract attention. The player can use it to make enemies go towards an place and escape from the other side.
* A device that makes the place partially invisible when standing next to objects.
* The player will be able to run (but that will generate more noise)
* A teleport device
* Hiding in the shadows (I don't know if this will be hard to implement -- I hope it isn't)

 

The enemies will use a path finding algorithm like A*.
A physics engine will be used for collision detection.

 

Note: I haven't started making the game yet (I haven't even finished the game design document for it).

---------------------------
Now the important question.
Given that I finish the above game in year's time and with the games I have already made,
will I be eligible (is this the word?) to get a job?

Thanks a lot for your time.

 

In the image above, I have put in red rectangle two pixels that are rendered black when they should not. I have made some debugging and found out that in those cases, the surface normal is pointing at the wrong direction. When I did n = -n the pixel gained its correct color (however If I do it for all pixels, all those correct will become wrong)

 

This is the code in which the surface normal is calculated. It is in the Triangle class (the torus is made of triangles - I import the model).

The calculation for the surface normal is at the top. Any ideas why the its direction is wrong? (it points at the opposite direction than it should).

override bool hit(const ref Ray r, float p0, float p1, ref HitInfo hitInfo)
	{
		// (e + td - a) . n = 0
		// ... t(d.n) + e.n - a.n = 0
		// we need to solve as t to find the solution
		// t = (dot(a, n) - dot(e, n)) / dot(d, n);
		// and because dot product is distributive,
		// we can write t = dot(a-e,n) / dot(d,n)

		Vector3 temp0 = b-a, temp1 = c-a;
		Vector3 n = cross(temp0, temp1); // calculate the normal of the plane that the triangle is on
		n.normalize();
		
		// TODO: r.d may have to be normalized?
		
		// if the normal and the ray are parallel, there's no intersection
		float dDotN = dot(r.d, n);
		
		// TODO: this might be causing accuracy problems. I should check it out
		if( dDotN == 0 )
			return false;
		
		// find the intersection point P with the plane
		const Vector3 aMinusR = a-r.e;
		float t = dot(aMinusR, n) / dDotN;
		Vector3 p = r.e + r.d * t;
		
		// now we need to test if the point is inside the triangle
		
		// 1) test if its in the negative subspace of vector ab
		Vector3 ab = b-a;
		Vector3 ap = p-a;
		Vector3 c1 = cross(ab, ap);
		c1.normalize();
		
		Vector3 ac = c-a;
		Vector3 c2 = cross(ab, ac);
		c2.normalize();
		
		immutable E = 0.01f;
		
		if( abs(c1.x - c2.x) > E || abs(c1.y - c2.y) > E || abs(c1.z-c2.z) > E )
			return false;
		
		// 2) test if its in the negative subspace of vector bc
		Vector3 bc = c-b;
		Vector3 bp = p-b;
		c1 = cross(bc, bp);
		c1.normalize();
		
		Vector3 ba = b-a;
		c2 = cross(ba, bc);
		c2.normalize();
		
		if( abs(c1.x - c2.x) > E || abs(c1.y - c2.y) > E || abs(c1.z-c2.z) > E)
			return false;	
		
		// 3) test if its in the negative subspace of vector ca
		Vector3 ca = a-c;
		Vector3 cp = p-c;
		c1 = cross(ca, cp);
		c1.normalize();
		
		Vector3 cb = b-c;
		c2 = cross(ca, cb);
		c2.normalize();
		
		if( abs(c1.x - c2.x) > E || abs(c1.y - c2.y) > E || abs(c1.z - c2.z) > E )
			return false;
		
		hitInfo.t = t;
		hitInfo.hitPoint = p;
		hitInfo.surfaceNormal = n;
		hitInfo.hitSurface = this;
		hitInfo.ray = r.d;
		
		//import std.stdio;
		//writeln("in triangle hit");
		
		return true;
	}

 

 

Hi. To improve the performance of my raytracer, I decided to use  Uniform Space Partitioning. Basically, I divide the world into 3D boxes, and put objects (Surfaces) inside them. When tracing a ray, I check first with the boxes and if there is a hit, I check with the Surfaces it contains.

 

The problem is, from 11 seconds I dropped to only 8 seconds. Another thing I noticed is that when the world is divided into more boxes, it takes more time to render. So this means there is a problem with my AABB-Ray collision function.

 

bool intersects(const ref Ray r) const
	{
		Vector3 n = void,						// normal
				v = void, u = void;				// vectors
		
		float t = void;
		
		// plane 0 (front)
		v = Vector3(max.x, min.y, min.z) - min;
		u = Vector3(min.x, max.y, min.z) - min;
		n = cross(v, u);
		n.normalize();
		t = dot(r.d, n);
		
		/++writeln("t0 = ", t);
		if( t > 0 )
			writeln("plane 0 intersected");
		else
			writeln("plane 0 not intersected");++/
		
		Vector3 temp = min - r.e;
		Vector3 p = r.e + r.d * dot(temp, n) / t;
		//writeln("p0 = ", p);
		if( p.x >= min.x && p.x <= max.x && p.y >= min.y && p.y <= max.y && p.z >= min.z && p.z <= max.z )
		{
			//writeln("YES 0\n");
			return true;
		}
		/++else
			writeln("NO 0\n");++/
		
		
		// plane 1 (right)
		v = Vector3(max.x, max.y, min.z) - Vector3(max.x, min.y, min.z);
		u = Vector3(max.x, min.y, max.z) - Vector3(max.x, min.y, min.z);
		n = cross(v, u);
		n.normalize();
		
		t = dot(r.d, n);
		/++writeln("t1 = ", t);
		
		if( t > 0 )
			writeln("plane 1 intersected");
		else
			writeln("plane 1 not intersected");++/
		
		temp = Vector3(max.x, min.y, min.z) - r.e;
		p = r.e + r.d * dot(temp, n) / t;
		//writeln("p1 = ", p);
		if( p.x >= min.x && p.x <= max.x && p.y >= min.y && p.y <= max.y && p.z >= min.z && p.z <= max.z )
		{
			//writeln("YES 1\n");
			return true;
		}
		/++else
			writeln("NO 1\n");++/
		
		// plane 2 (left)
		v = Vector3(min.x, min.y, max.z) - Vector3(min.x, min.y, min.z);
		u = Vector3(min.x, max.y, min.z) - Vector3(min.x, min.y, min.z);
		n = cross(v, u);
		n.normalize();
		
		t = dot(r.d, n);
		/++writeln("t2 = ", t);
		
		if( t > 0 )
			writeln("plane 2 intersected");
		else
			writeln("plane 2 not intersected");++/
		
		temp = Vector3(min.x, min.y, min.z) - r.e;
		p = r.e + r.d * dot(temp, n) / t;
		//writeln("p2 = ", p);
		if( p.x >= min.x && p.x <= max.x && p.y >= min.y && p.y <= max.y && p.z >= min.z && p.z <= max.z )
		{
			//writeln("YES 2\n");
			return true;
		}
		/++else
			writeln("NO 2\n");++/
		
		// plane 3 (back)
		v = Vector3(max.x, min.y, max.z) - Vector3(min.x, min.y, max.z);
		u = Vector3(min.x, max.y, max.z) - Vector3(min.x, min.y, max.z);
		n = cross(v, u);
		n.normalize();
		
		t = dot(r.d, n);
		/++writeln("t3 = ", t);
		
		if( t > 0 )
			writeln("plane 3 intersected");
		else
			writeln("plane 3 not intersected");++/
		
		temp = Vector3(min.x, min.y, max.z) - r.e;
		p = r.e + r.d * dot(temp, n) / t;
		//writeln("p3 = ", p);
		if( p.x >= min.x && p.x <= max.x && p.y >= min.y && p.y <= max.y && p.z >= min.z && p.z <= max.z )
		{
			//writeln("YES 3\n");
			return true;
		}
		/++else
			writeln("NO 3\n");++/
		
		// plane 4 (top)
		v = Vector3(min.x, max.y, max.z) - Vector3(min.x, max.y, min.z);
		u = Vector3(max.x, max.y, min.z) - Vector3(min.x, max.y, min.z);
		n = cross(v, u);
		n.normalize();
		
		t = dot(r.d, n);
		/++writeln("t4 = ", t);
		
		if( t > 0 )
			writeln("plane 4 intersected");
		else
			writeln("plane 4 not intersected");++/
		
		temp = Vector3(min.x, max.y, min.z) - r.e;
		p = r.e + r.d * dot(temp, n) / t;
		//writeln("p4 = ", p);
		if( p.x >= min.x && p.x <= max.x && p.y >= min.y && p.y <= max.y && p.z >= min.z && p.z <= max.z )
		{
			//writeln("YES 4\n");
			return true;
		}
		else
			/++writeln("NO 4\n");++/
		
		// plane 5 (bottom)
		v = Vector3(max.x, min.y, min.z) - Vector3(min.x, min.y, min.z);
		u = Vector3(min.x, min.y, max.z) - Vector3(min.x, min.y, min.z);
		n = cross(v, u);
		n.normalize();
		
		t = dot(r.d, n);
		/++writeln("t5 = ", t);
		
		if( t > 0 )
			writeln("plane 5 intersected");
		else
			writeln("plane 5 not intersected");++/
		
		temp = Vector3(min.x, min.y, min.z) - r.e;
		p = r.e + r.d * dot(temp, n) / t;
		//writeln("p5 = ", p);
		if( p.x >= min.x && p.x <= max.x && p.y >= min.y && p.y <= max.y && p.z >= min.z && p.z <= max.z )
		{
			//writeln("YES 5\n");
			return true;
		}
		/++else
			writeln("NO 5\n");++/
		
		return false;
	}

What I do is check all six planes and then if the hit point is inside the boundaries. I know this is the worst method. What's a better way to do this?

 

Please, if you suggest something, provide an explanation why it works, as that's the important thing here - I want to learn this stuff.

Thank you

Hi, I want to make my raytracer able to trace triangles, not only spheres as it currently does.

So I must first check if the ray hits the plane.

Leaving aside the triangle for now,
I have:

Vector3 a = {0, 0, 0}; // a point of the plane
Vector3 n = {0, 1, 0}; // the plane's normal
n.normalize();

Vector3 e = {0, -1, 0}; // the starting point of the ray
Vector3 d = {0, 1.0f, 0}; // the ray's direction
d.normalize();

float t = (dot(a, n) - dot(e, n)) / dot(d, n);

So, the collision point would be e + t * d.
Also, if dot(d, n) = 0, the ray and the plane are parallel.

Is that correct?