collision detection with prerendered background

Java 2D
#1

Trying to figure out the best way to do collision detection with a pre-rendered background. I understand that you should have a collision polygon, but I am not sure how would you test against the poly with a sphere or iso tile.

http://www.angelfire.com/clone/wolfbane/ex1.jpg

lets say the blue shape is the collision polly and the red box is the object that cannot pass through it. What type of collision detection should I do? I am thinking that I should store the line equations of each part of the collision poly and then test a point on the box against a relevent point on the polly that I could find through the equations. Thats how I did it when I wrote my iso tile collision algorythm. Problem with that is how do I know when to do the test. In my iso tile collision I tested when two bounding boxes intersected.
Anyone know how poly collision is done when using pre rendered backgrounds? I read somewhere that the poly could be made to do a check if anyone is populationg its “solid” part, but I am prob wrong.

#2

Theres lots of geometry intersection methods, with varying degrees of speed and accuracy. A few random suggestions:

For the example above, I’d create line segments for the movement of every vertex on the square from its previous and current positions (like a swept collision volume, but just done on the corners). Then check these line segments against the segments on the background poly. You also need to do the reverse - check the blue points (swept over the reverse of the red’s movement) against the edges of the red square.
The nice thing about this is that you can’t get the square ‘leapfrogging’ the blue poly if it moves at fast speeds or the blue poly is thin. Its robust, accurate and gives you handy information on where the collision actually occured.

You may want to make things easier for yourself by forcing the background collision objects to be convex hulls, as this simplifies collision (and you can just use several ones to get the same complexity). It also provides easier in/out testing, and you can use axis-aligned bounding boxes as early checks if need be (you could always do that with the current one as well, but with convex hulls the bounds fit much tighter for the most part).

If you want really complex objects, then just scan convert them at a suitable resolution and check for pixel overlap. A bit brute force ish, but could be much faster if you have lots of small edges to check against (plus you could pre-create the background collision map and reuse it).

#3

[quote]I’d create line segments for the movement of every vertex on the square from its previous and current positions (like a swept collision volume, but just done on the corners).
[/quote]
What do you mean by this exactly? Can you elaborate a bit more maybe with an example?

#4

http://studenti.lboro.ac.uk/~cojc5/Temp/Col.png

Now lets say the dark red is the previous position, and the bright red the new position, moving in the direction of the purple arrow.

You take each point of the original shape and make a line segment from it from old to new (the purple lines). This is pretty simple since you just use the same method that you moved the entire shape by for each point individually.

Then you can just test these segments against the collision polys edges. You can see how the top right purple segment will intersect one of the blue lines. The intersection also gives you the point of collision.

You need to repeat the check in reverse to get it robust (move blue polys points by the inverse of the movement and check their swept line segments). If you don’t you can miss certain situations (like if the dark red were to move left now, and bump into the pointy bit).

#5

I take it that by swept collision you mean using the entire sides instead of the points? I am also guessing that using a circle for the collision “box” would be a lot easier than using an actual box in this case? Also this line check is done every frame regardless of the location of the box, right?

#6

If these are iso tiles then there’s a simpler solution.

Each tile is flagged with blocking/non-blocking. When you store the map you store a list of blocked tile locations. When you do your A-Star the first thing you do is mark all the blocked tiles as unaccessible in your A-star map.

#7

Thats how I have been doing it. But I had a design change and decided to go with keyboard controlled movement of the main char (ala FF3). Still keeping everything isometric, I wrote collision detection for iso tiles based on line equations and bounding boxes. This works for now, but as I started designing large area maps I decided to look into alternatives.
Also, my main charater is player controlled but the npc’s still move around freely and need to be able to seek out my charater. This is my other challenge. I was wonering if anyone knew how movement was done in Baldur’s Gate? I know they ued collision polys, bu did they use a grid and A*. (I konw the pathfining was really bad in that game but thats besides the point)

#8

Using boxes you just have to code line-line collisions and from that one thing you can do a lot. Finding the intersection of two line segments is easy enough. So you can find intersections along bounding box edges and intersections along path vectors. (the line segment from the previous corner position to the new corner position)

That would usually be enough to catch most collision cases. Though geometry details and speed could mean that no line segments (spatial or temporal vectors) intersect with anything between two frames, yet the objects involved would have had to pass through each other.