pathfinding, targetting, and collisions when the world wraps

Game Mechanics Artificial Intelligence
#1

I am currently working on a game where the world will have a fixed size say 2000x4000, but there will be no boundaries. When you get to one edge you just wrap around to the other side.

I have visibility of objects working OK. When you can see 0,0 and 2000,4000 at the same time, objects in all the corners draw in their proper relative positions, but I am sort of brute forcing it. I check x,y x+2000,y x+2000,y+4000 and x,y+4000 to see if any of those locations are visible.

Do I need to do something similar for collisions? Right now, if the bounding circle of an object crosses the world boundary, it won’t register a collision with an object on the other side, and the two can penetrate and overlap. I am concerned a bit about performance as I am treating each object as if it was in four different places for drawing and that would cause a lot of collision checks. For objects to register a collision they would need to check if any one of their four positions collided with any one of another objects four positions. I might be able to limit that to only doing the extra checks to when the bounding box crosses a boundary.

And that brings me to path finding. For that, I feel I am going to need four positions for every object all the time in order to find the shortest path between two of them for the computer AI to chase and target properly.

I am hoping I am waaay of base and there is a much less computationally intensive way to solve this problem.

Any help would be appreciated.

#2

What you need to do is to represent your world differently. Right now you’re seeing it sort of as an array - when you get to the edge you fall off. What would probably be better for your purposes would be to create a bunch of links. Have each tile have pointers to its north, south, east, and west, connections, then you can just connect the ends to each other. For pathfinding and whatnot, this will work perfectly. Then for drawing, you simply create a recursive function (or something similar), that draws all grid spaces that are an X distance of i away from the player, and a Y distance of j. In this case, the drawing becomes more processor intensive than it was before, but collision and pathfinding are very fast. You could try combining the two by storing every room in an array but also allowing them to link to their neighbors.

You can also simply turn array access into a function. Instead of saying array[m][n], you would say, getArray(m,n), and then make your function like this:


public Object getArray(int i, int j)
{
     try
     {
          return array[i][j];
     }
     catch (ArrayIndexOutOfBoundsException e)
     {
          if (i >= array.length)
               i = 0;
          else if (i < 0)
               i = array.length-1;
          if (j >= array[0].length)
               j = 0;
          else if (j < 0)
               j = array[0].length-1;
          return array[i][j];
     }
     return null;
}

Here any invalid array locations are automatically “wrapped” back to the other side. This is more of a hacky solution, but it might suit your purposes.

#3

Thanks for the reply, but it looks like I need to be a bit more clear about what I am doing.
The world isn’t tile based at all, and there are no rooms. Think asteroids where you wrap from one side of the monitor to the other. Except in mine, the world is larger then what is displayed on the monitor.
Have a look at this partial screenshot The red line is the world boundary.
I can move across the edges just fine. Collisions don’t work properly if the bounding circle overlaps the edge. ie The objects don’t wrap until their centers cross the edge.
All objects have an x,y location (where x and y are doubles) and an associated velocity which has both the angle/magnitude of movement and double x and y components of the movement.
At the moment, I just have the list of objects to work with.

#4

Okay, got it. You’re right that this way things get a bit more complicated, but not too much so.

All you need to do is represent collision as a total geometry - when the ship moves over an edge, subtract the part off the screen from that edge and move it to the other side, then union the two parts. I’m not sure how you’re handling collisions, but you can always use Java’s Area class to handle the geometry for you.

#5

Actually, it helps to think about it like the monitor was the entire world. When I am crossing the edge I am on both sides at the same time (or all four if I hit the corner).
I think I can get away with doing an extra check (or three) if my bounding circle crosses an edge. Essentially, when it is crossing the edge it is in up to four locations at the same time. I think the easiest way to do that is going to be to modify the GameObject to support the idea of a temporary object that is only allowed to exist as long as it is overlapping the world bounds. This temporary object would have a “parent” object that it is linked to and when the either the parent or the temporary object has a collision, both objects would have their movement vectors updated. It is a big enough world that there shouldn’t be more than two or three objects crossing the edge at once, so it shouldn’t be a big performance hit.

This is what I am currently doing to test for collisions. If I add the temporary object, I won’t have to change this at all.

	public double testCollision(GameObject b, double t, List<GameCollision> collisions) {
		GameVector movea = velocity.scale(t);
		GameVector moveb = b.velocity.scale(t);
		double deltaX = b.center.x - center.x;
		double deltaXSquared = deltaX * deltaX;
		double deltaY = b.center.y - center.y;
		double deltaYSquared = deltaY * deltaY;
		int sumRadii = radius + b.radius;
		int sumRadiiSquared = sumRadii * sumRadii;
		double distSquared = deltaXSquared + deltaYSquared;
		GameVector movec = movea.subtract(moveb);
		if (movec.getLength() < Math.sqrt(distSquared) - (double)sumRadii) {
			return t;
		}
		GameVector N = movec.normal();
		GameVector C = center.toGameVector(b.center);
		double D = N.dot(C);
		double lengthC = C.getLength();
		double F = lengthC*lengthC-D*D;
		if (F >= (double)sumRadiiSquared) {
			return t;
		}
		double T = (double)sumRadiiSquared-F;
		if (T < 0.0D) {
			return t;
		}
		double distance = D - Math.sqrt(T);
		double mag = movec.getLength();
		if (mag < distance) {
			return t;
		}
		double collision_t = (distance/mag)*t;
		if (collision_t < 0.0D || collision_t > t) {
			return t;
		} else {
			collisions.add(0, new GameCollision(this, b, collision_t));
			return collision_t;
		}
	}

The problem I was trying to avoid was with the enemies finding their optimum attack vector. It looks like for that, the ship and the enemies will each need four locations all the time and I will need to find the shortest permutation. 4! = 24, but with symmetry I can drop that to 12. 12 distance calculations per enemy, this is probably going to be my performance bottleneck

#6

Yeah, that will be a pretty big hit to performance. Why not improve your actual collision algorithm? You can put everything in “buckets” and then use a sort of quad tree algorithm to speed collision implementation. I can’t see a game like that creating much of a collision bottleneck as long as you are using smart algorithms, even if you’ve got 4 collision tests per object. Simply start with location buckets (like a 10x10 array of lists of objects within those quadrants), then use AABB (Axis Oriented Bounding Box) collision, then use geometry collision. Because you narrow things down along the way, you don’t have to do the expensive geometry collision except for very close objects.

#7

I am not sure that the collision algorithm is going to be the issue. I am checking every object against every other object to see if they will move to or past collision in the next time tick, but I have not figured out pixel level collision detection yet, so it is simply bounding circle. I can try the spacial hashing, but I will have to deal with my edge problem in every hash bucket. I will need to add objects that overlap hash edges to all the buckets they overlap. Any recommendations on bucket size or number of buckets? Two few, and I don’t get any benefit, too many and I have a lot of overhead checking for non-empty buckets.

I think I may have just thought of a trick I can use to solve the issue of finding the shortest attack vector. If I translate the player’s ship to the center of the map and apply the same relative transformation to the enemy ships, then the distance should be accurate.

So, in the example I posted a picture for, let’s assume the asteroid is an enemy :wink:
The ship was at 36, 5936 and the center of the map is at 2400, 3000 so the ship needs to move by 2364, -2936
The “enemy” was at 4653, 44 and applying the same transformation puts it at 7017, -2892.
Bringing those coordinates back into the world gets me 2217, 3108
That’s a dx of 183 and a dy of 108 for a distance of 212.492.
Yay! it works. ;D
So two transformations and two mod operations beats 12 separate distance calculations.

#8

Yeah, you don’t really need to translate anything, though, do you? Just use the absolute value.

As for the buckets, probably a 10x10 grouping would be good. You can add the same object to 4 different buckets if you want, it won’t be a big deal. Either way, you’re only checking a couple buckets at the maximum so you’ll ignore the extra objects.

Even so, if you’re just doing radial collision than I’m not sure you even have to worry about it all. Doing the absolute worst algorithm with a bunch of wasted comparisons will probably still be plenty fast for a game of this size unless you’ve got hundreds or thousands of objects on the screen at a time.

#9

Not sure what you mean here. Using original positions and absolute value I get the following:
dx = 4617
dy = 5892
which is a distance of 7485.4761 and an attack vector going in pretty much the opposite direction of what it should.

That is what I was thinking as my object count is going to be low, probably less than 100. But I can try it out and see if I get any benefit.

#10

Maybe I don’t entirely understand you exact project. I just don’t understand why screen wrapping changes the distance from one object to another.

#11

Trying two more pictures.
In this image, the red lines are the edges of the world where they have wrapped together. The green box is the view of that world seen in the game.

http://farm4.static.flickr.com/3097/2760921994_5a55414e50.jpg

And this one is just of the world.

http://farm4.static.flickr.com/3069/2760078085_fba2e6f2f3.jpg

Can you see how wrapping impacts the distance/direction calculations now?

#12

Yes! That’s obvious, I just wasn’t using my brains. :stuck_out_tongue:

Seems like your solution is a good one, then. You can also base the distance calculation upon which edge the ship is closest to, but the end result and processor required is the same.

#13

To avoid having to do this 4 times (or to have temporary objects) you just need to normalise the deltas. As long as the sum of the radii of the objects is less than half the dimension length (call this L), then you can just normalise the delta values to be in the range -L/2 … L/2.

e.g.


	double deltaX = b.center.x - center.x;
	if( deltaX < -L/2 )
		deltaX += L;
	else if( deltaX > L/2 )
		deltaX -= L;

This will end up choosing the closest point of the 4 that are possible. Then you just need do the hit test once as described.

Cheers, Tim.

#14

Awesome, thanks for that one.

I had to change another spot in a similar fashion. The actual centers of the objects were being used to make a vector. It works like a charm now.

		GamePosition cTemp = center;
		GamePosition bTemp = b.center;
		if (cTemp.x > (worldBounds.width / 2)) {
			cTemp.x -= worldBounds.width;
		}
		if (cTemp.y > (worldBounds.height / 2)) {
			cTemp.y -= worldBounds.height;
		}
		if (bTemp.x > (worldBounds.width / 2)) {
			bTemp.x -= worldBounds.width;
		}
		if (bTemp.y > (worldBounds.height / 2)) {
			bTemp.y -= worldBounds.height;
		}
		GameVector C = cTemp.toGameVector(bTemp);
#15

I’m not convinced that the above code will actually work I’m afraid. It’s important that it’s the DELTAS that are normalised. I.e. the values AFTER the subtraction.

I think you’ll find that your code above will now fail if, for example, A.x is just smaller than L/2 and B.x is just greater than L/2. A would end up heading left to get to B, when it should be heading right. You’ve just moved the problem from the boundaries of the space to the centre. :slight_smile:

Perhaps this would be more correct:


		GameVector C = center.toGameVector(b.center);
		if (C.x > (worldBounds.width / 2)) {
			C.x -= worldBounds.width;
		}
		if (C.x < (-worldBounds.width / 2)) {
			C.x += worldBounds.width;
		}
		if (C.y > (worldBounds.height / 2)) {
			C.y -= worldBounds.height;
		}
		if (C.y < (-worldBounds.height / 2)) {
			C.y += worldBounds.height;
		}

Cheers, Tim.

#16

You are correct in that I now have issues at the center of the world.
The values for center.x and center.y will never be negative, so the additional checks you suggest will never happen.
And the direction of that vector is important as it is being used to determine if the collision will happen within the given time tick.
Maybe I need to work on copies of the objects and translate one of them to world center and apply the same transformation to the other. I don’t think actual position will impact the calculations as long as relative positions remain constant.

#17

True. (well, this is what I had assumed anyway :slight_smile: )

False – assuming that

GameVector C = center.toGameVector(b.center)

is calculating the difference of the two vectors involved.

i.e. doing the same kind of thing as the following pseudocode…


C.x = b.center.x - center.x;
C.y = b.center.y - center.y;

The code isn’t checking center.x against -L/2 … its checking C.x [which I assume is (b.center.x - center.x)] against -L/2.

Given two variables, A & B, whose range is [0…N], (A-B) has range [-N…N], which can definitely be negative if N > 0.

So long as the subtractions to calculate the deltas (i.e. relative vectors – both position and velocity) are both done the same way around, the relative signs should be correct. And as long as the delta-velocity isn’t too high (i.e. abs(deltaV.x) * t < L/2, etc.) then the collision time calc should work as expected too.

Cheers, Tim.

#18

Ah, I had missed that you were working on the vector.
Solution actually got much simpler, I can just re-use the previously calculated deltas to make the vector.

		GameVector C = new GameVector(deltaX,deltaY);

And now all works like a charm, edges and center.

Thanks again.