/sci/ - Science & Math

[Anonymous No.3684671]

How did old PC games implement real-time collision detection for a world of many objects? It seems like the algorithm had to be very efficient for the computers of that time to process in real time (the game pictured ran on a 486 66 MHz PC with 8 MB RAM). Any hints?

[Someone !1LTek3FWf. No.3684690]

Rollercoaster tycoon was made in Assembly. that game run pretty fast. That may be a hint.

[Anonymous No.3684688]

>2D game
>efficient algorithm

[Anonymous No.3684692]

I HAVE NO IDEA.
But here goes:
They just made invisible walls and said "true for all ->x".
This was an uninformative bump.

[Anonymous No.3684702]

>>3684692
I really mainly meant object-to-object collision.

[Anonymous No.3684710]

graphs

[Anonymous No.3684728]

>>3684702
Well then the objects could be defined as "walls" that you cant cross. Right? One jeep touches another jeep. Nope. Both defined as walls.

Sounds legit to me. But wait for someone who knows what they're talking about. I have no idea.

[Anonymous No.3684742]

http://en.wikipedia.org/wiki/Bounding_volume
Invisible boxes.

[Someone !1LTek3FWf. No.3684746]

Not op but there's also this
http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf

[Anonymous No.3684747]

>>3684671
Space partitioning? ie Only check against objects in your cell.

Why not disassemble the code and find out? I think you can still get a free (legit) version of IDA.

[Anonymous No.3684751]

The map was split into a grid. Each part of the grid can only contain one unit at a time. Then a form of the A* path-finding (or anything for that matter) algorithm is used to move the object. No collision detection needed, you just update the movement and then run the path finding.
Older games then compensated with various tricks, like recalculating the path every so or so frames to save space, or even recalculating only if an illegal move order is issued.

[Anonymous No.3684789]

>>3684751
Very interedasting, thanks

>>3684747
>check against objects in your cell
How do you know they're in there? You need another algorithm just for that, and I'm worried about efficiency still

[Someone !1LTek3FWf. No.3684786]

http://www.jongware.com/galaxy1.html

They don't make games like this anymore.

[Someone !1LTek3FWf. No.3684803]

>>3684786
in case tl;dr
>The Milky Way in Frontier:Elite 2/FFE (hence FFE since most of the algorithms are gleaned from there) is a highly random generated, yet self-containing system. Every 'random' star will be randomly created in exactly the same way every time you generate the Milky Way sector it is in, but you don't need to keep tabs on all 513,982,470 unique star systems in memory or even on disk.
>This is called a 'semi-random' system; every time you feed it the same seed you get the same result. (Note that it's not that different from the so-called 'random number generator' in various programming languages.)

[Anonymous No.3684939]

>>3684789
the map is made up of a 2 dimensional array of cells. when moving from one cell to another cell, you just check if the cell is empty. so if it's [row][column] and you're moving something upward you just do a check to see if [current-row+1][current-column] is empty. O(1) efficiency.

[Anonymous No.3684953]

>>3684939
I think I didn't answer your question well enough.

Cells are containers for objects. You don't check a list of objects to see if they're in the cell, you check one cell to see if it has the object in it, and when moving from cell to cell you transfer the object between the cells.

[Anonymous No.3684973]

>>3684789
divide the map into an (equally spread) number of nodes so that any object is at all times closest to only one node. then whenever you move an object to a node you only need to check it for collision with all other objects that have marked that node as "closest to me". this already prevents having to check on every object in the game world to see if it collides.

[Anonymous No.3684985]

>>3684953
And by object, I simply mean anything that could represent your object. So it could simply be a sequential ID for any object created at initialization of that object. You don't have to store the entire object in the cell.

[Anonymous No.3685048]

>>3684671
In games like CNC they did not have very complex collision detection, they just had a map of movable grid spots and added buildings, tanks and troops to the map as temporary blocks.
that way collision checking just involves checking the grid you want to move to for how full it is which took almost no times.
To find the path from point A to point B they would have use A* path finding, I do not remember how good the path finding was and I may be wrong here. They also would have done tricks, like running only a limited number of times path searches per frame, only check against static objects on the grid etc.
Another useful thing they did was analyze what functions where slowing the game down, and write those in assembly code. What primarily slows games down is when a function is not very optimized and get called multiple times per frame.

[Anonymous No.3685122]

I used this math formula for collision detection when I was trying to program games in c++. What does /sci/ think of it?
It is certainly more processor-intensive than the simpler collision detection methods as already presented in this thread.

http://hi.baidu.com/willor/blog/item/be5e3728bb1f50f998250a50.html

[Anonymous No.3685142]

They used a very good broad phase collision algorithm to keep neighbor searches local.

google:
broad phase collision
narrow phase collision
visual examples of broad phase collision:
http://www.youtube.com/watch?v=1ccmwlyTEJM

[Anonymous No.3685157]

This thread has proven to be very helpful. Thanks all

[Anonymous No.3685168]

>>3685122
yes it is more intensive, but what usually hurts more than the complexity of a collision detection is the number of collision detections, 2 objects makes 1 collision detection, 3 makes 3, 4 makes 6, 5 makes 10, 100 makes 4950.

[Someone !1LTek3FWf. No.3685174]

>>3685142
For a very informative video, it's a shame the volume goes very low.