LittleBear
says: An honest brew makes its own friends.
12.03.07
Collision Detection in Conway’s Life
How would you go about performing collision detection in Conway’s Life? First, though, let me step back a bit. Imagine Relentless Automata, but with a slight change. The player’s ship can now switch between the Conway world and the gameplay world.
This leads to the question of how to handle a ship in the Conway world. There are two ways as I see it, either the ship is a glider or it is a static pattern. If the ship is a static pattern, we can simply move the whole pattern. The other way, with the ship being a glider, we can trigger the iterations of the ship through user input. In this case it helps if we consider the local grid of the ship as somewhat overlayed on the Conway world’s grid.
Having a glider as the player’s ship is the more interesting case, and seems more in keeping with the spirit of such a game. But we do have to keep the pattern separate from the regular grid, otherwise it will “move” by itself. How then to capture a collision? I’m considering implementing a one-grid zone around the ship, and testing to see whether or not the regular grid affects that zone through the birth of new automata.
Or, perhaps something like capturing a subsection of the grid if something comes close. I could then combine the ship with the subsection, run a few iterations and see if anything survived? It’s a fairly interesting problem. Well, to me at least 
I’m going to try and rapid prototype some of this soon, to elicit feedback on whether handling a ship in Conway’s Life works makes any sense at all. The quality of the suggestions I received for DS4 have convinced me this is a better way than programming in isolation.
Lorenzo Gatti said,
March 13, 2007 at 8:42 am
“Having a glider as the player’s ship is the more interesting case, and seems more in keeping with the spirit of such a game. But we do have to keep the pattern separate from the regular grid, otherwise it will “move†by itself.”
The whole point of a glider is that it moves by itself; if it is player controlled it is actually a sprite on a pixel grid that correspond to the Life grid, and at best it looks and moves like a glider (and it can be confused with “natural” gliders).
I would give the player a large slow starship or (more plausibly) a static structure and alter/ move it by computer-assisted overwriting of cells. For example, “shooting” can consist of pasting gliders pointing in the appropriate direction as shots (they should move faster than the starship); firepower upgrades can consist of glider guns and ablative armour can consist of arrays of glider absorbers, and a lot of the action would revolve around countering incoming fire by placing shields and shots.
Object identity would be very fuzzy; the ship should be considered alive if after its period a large fraction of the cells at its supposed location match the template.
the2bears said,
March 13, 2007 at 9:21 am
“The whole point of a glider is that it moves by itself; if it is player controlled it is actually a sprite on a pixel grid that correspond to the Life grid, and at best it looks and moves like a glider (and it can be confused with “natural†gliders).”
But a static pattern is the same if you “force” the movement. I know gliders are by definition self-moving, I just want the control of an instance in the hands of the player. Point it in the direction you want to move, then “up arrow” triggers an iteration of the pattern. It’s like having a Life grid where generations are triggered by the user. Arrow keys trigger “computer-assisted” adjustments to orientation, or the next generation.
Either way I’d like the pattern that is the ship to interact with the “real” Conway grid, and that’s what causes a few problems. I think I’ll have to keep a complete second copy of the Conway grid, add the player ship, iterate, then check if it’s still there (or partially there as you suggest). If it’s hit, bring it up to the surface and make it ‘splode
And yes, shooting would consist of dropping gliders into the grid, allowing them to disrupt the environment.
I’m not so sure about having powerups in the Conway world. It’s not the primary field of action, but a secondary one. Picture a Gosper Glider Gun generating away, those gliders “jumping” to the surface/gameplay world and attacking. The only way to win the fight, eventually, is to dive down to the Conway world and disrupt the Gun. At least that’s my theory
Bill
cliftut said,
March 16, 2007 at 5:59 pm
An idea for a style of play or another game mode (?) would be to have the Life patterns ‘paint’ solid blocks onto the ‘physical’ level. That’s just a quick thought though.
About collision; I had an idea that something might be possible by projecting a copy of the ship onto the conway level, but i suppose that wouldn’t work; you’d constantly have life patterns spawning away from the ship…
What I’m really thinking is that you could have some sort of sensors that tell the computer when there are live life pixels occupying the same space as the ship. Perhapse depending on the percentage of the ship these pixels are occupying, there could be different results.
i.e.
20% or less =light damage (ussuming there is health involved)
21% to35% =medium damage
35% to 50% =heavy damage
If this is going to work as a hit=kill type of thing, then percents wouldn’t be necessary, and whether this would work would also depend on the size of the ship.
There’s my two cents.
the2bears said,
March 16, 2007 at 6:56 pm
Some nice ideas, and I want to say I really appreciate both Lorenzo’s comments and yours, cliftut.
I think it’s fairly straight-forward doing something like “occupying the same space”, it’s whether or not there’s actual interaction. What I mean is, the idea is the ship can be in either the Conway world or the game world, and the behaviour I’m trying to figure out is the former.
I still intend to have patterns recognized/matched from the Conway world and spawned “up” to the game world, as I originally intended. Just got to get some samples of the behaviour out there for people to test and see how it feels.
Bill
rascunho » Blog Archive » links for 2007-03-18 said,
March 18, 2007 at 12:21 pm
[...] the2bears.com » Collision Detection in Conway’s Life How would you go about performing collision detection in Conway’s Life? First, though, let me step back a bit. Imagine Relentless Automata, but with a slight change. The player’s ship can now switch between the Conway world and the gameplay world. (tags: http://www.the2bears.com 2007 collision_detection conway gameai shooter jogo_da_vida blog_post) [...]
ornahfloalo said,
January 10, 2008 at 8:43 am
=”http://www.xrum.977mb.com”>new year foto