| --- Log opened Sat Aug 01 00:00:32 2009 |
| 00:05 | | crem [~moo@Nightstar-28703.adsl.mgts.by] has joined #code |
| 00:14 | | You're now known as TheWatcher[T-2] |
| 00:16 | | You're now known as TheWatcher[zZzZ] |
| 03:47 | | gnolam [lenin@Nightstar-1382.A163.priv.bahnhof.se] has quit [Quit: Z?] |
| 05:47 | <@Consul> | Heh |
| 05:48 | <@Consul> | I used my "You've Got Questions, We've Got Blank Stares" joke on Twitter, in reference to Radio Shack, and the RS Twitter account spotted me and replied. A rather snarky one, too, I might add. I'm kinda impressed. |
| 05:50 | <@Consul> | "You have questions, and we have bleeding edge computer scientists answering them online. Sorry we haven't perfected cloning yet." |
| 06:03 | | Alek [~omegaboot@Nightstar-6528.dsl.emhril.sbcglobal.net] has quit [Quit: ] |
| 06:04 | | Syloqs-AFH [~Syloq@ServicesAdmin.Nightstar.Net] has quit [Connection reset by peer] |
| 06:06 | | Alek [~omegaboot@Nightstar-6528.dsl.emhril.sbcglobal.net] has joined #code |
| 06:13 | | crem [~moo@Nightstar-28703.adsl.mgts.by] has quit [Ping Timeout] |
| 06:35 | | AnnoDomini [AnnoDomini@Nightstar-29640.neoplus.adsl.tpnet.pl] has joined #Code |
| 06:36 | | mode/#code [+o AnnoDomini] by ChanServ |
| 06:50 | | Thaqui [~Thaqui@121.98.166.ns-22683] has joined #code |
| 06:50 | | mode/#code [+o Thaqui] by ChanServ |
| 06:53 | | crem [~moo@Nightstar-28703.adsl.mgts.by] has joined #code |
| 08:03 | | Derakon is now known as Derakon[AFK] |
| 08:31 | | Rhamphoryncus [~rhamph@Nightstar-7168.ed.shawcable.net] has joined #code |
| 08:40 | | crem [~moo@Nightstar-28703.adsl.mgts.by] has quit [Quit: Ep0xa 1.2v] |
| 09:34 | | Vornicus is now known as Vornicus-Latens |
| 09:46 | | Consul_ [~Consul__@Nightstar-2555.dsl.sfldmi.ameritech.net] has joined #code |
| 09:46 | | Consul [~Consul__@Nightstar-2425.dsl.sfldmi.ameritech.net] has quit [Ping Timeout] |
| 10:12 | | You're now known as TheWatcher |
| 11:35 | | Attilla [~The.Attil@92.1.130.ns-26400] has joined #code |
| 11:35 | | mode/#code [+o Attilla] by ChanServ |
| 12:33 | | Rhamphoryncus [~rhamph@Nightstar-7168.ed.shawcable.net] has quit [Quit: Rhamphoryncus] |
| 12:45 | | Netsplit DeepThought.NY.US.Nightstar.Net <-> Blargh.CA.US.Nightstar.Net quits: Namegduf, @Thaqui, Alek, Kazriko |
| 12:49 | | Netsplit over, joins: Alek |
| 13:29 | | Kazriko [~kazrikna@Nightstar-26123.gdj-co.client.bresnan.net] has joined #code |
| 13:29 | | Thaqui [~Thaqui@121.98.166.ns-22683] has joined #code |
| 13:29 | | mode/#code [+o Thaqui] by ChanServ |
| 13:29 | | Namegduf [namegduf@82.25.200.ns-12231] has joined #code |
| 13:59 | | You're now known as TheWatcher[afk] |
| 14:18 | | gnolam [lenin@Nightstar-1382.A163.priv.bahnhof.se] has joined #Code |
| 14:18 | | mode/#code [+o gnolam] by ChanServ |
| 15:07 | | Attilla [~The.Attil@92.1.130.ns-26400] has quit [Quit: ] |
| 15:36 | | Attilla [~The.Attil@92.1.130.ns-26400] has joined #code |
| 15:36 | | mode/#code [+o Attilla] by ChanServ |
| 16:27 | | Derakon[AFK] is now known as Derakon |
| 18:02 | | Vornicus-Latens is now known as Vornicus |
| 18:10 | | You're now known as TheWatcher |
| 18:11 | <@TheWatcher> | Idly, Dera? |
| 18:13 | | Consul_ [~Consul__@Nightstar-2555.dsl.sfldmi.ameritech.net] has quit [Quit: Leaving] |
| 18:13 | <@TheWatcher> | Regarding your last entry, and the whole critter sim thing. Do you think it might be possible to have several levels of sim, so that critters off-screen out to some range still get simulated, but don't need to do as much or as often, and ones outside that range are removed? |
| 18:13 | | Consul [~Consul__@Nightstar-2555.dsl.sfldmi.ameritech.net] has joined #code |
| 18:13 | | mode/#code [+o Consul] by ChanServ |
| 18:14 | <@TheWatcher> | That might buy you a little speed increase, without the problem you mention |
| 18:33 | <@Derakon> | TW: I responded to your comment. :) |
| 18:33 | <@Derakon> | As for having various levels of sim, the most costly part is collision detection and that's the part that I don't think I can reasonably skimp on. |
| 18:34 | | * TheWatcher nods |
| 18:34 | <@TheWatcher> | Can you reduce the frequency based on the distance, is more my question? |
| 18:35 | <@Derakon> | I could probably rig something, but that sounds like a premature optimization to me. :) |
| 18:35 | <@Derakon> | Certainly, though, some creatures will be responsive -- they won't take action until the player gets close enough to pounce on. |
| 18:40 | | Derakon [~Derakon@Nightstar-5824.hsd1.ca.comcast.net] has quit [Quit: Leaving] |
| 18:43 | | Derakon [~Derakon@Nightstar-5824.hsd1.ca.comcast.net] has joined #code |
| 18:43 | | mode/#code [+o Derakon] by ChanServ |
| 19:29 | | Rhamphoryncus [~rhamph@Nightstar-7168.ed.shawcable.net] has joined #code |
| 19:32 | | Syloqs_AFH [~Syloq@Admin.Nightstar.Net] has joined #code |
| 19:33 | | Syloqs_AFH is now known as Syloqs-AFH |
| 19:46 | | Thaqui [~Thaqui@121.98.166.ns-22683] has quit [Client exited] |
| 19:59 | | * Derakon ponders collision detection. |
| 19:59 | <@Derakon> | Here's my current "root-level" update function for a single object: http://paste.ubuntu.com/242390/ |
| 20:00 | <@Derakon> | checkTerrain() checks the object against nearby terrain blocks, naturally. |
| 20:01 | <@Derakon> | Problem is, now I want to have non-terrain objects hitting each other, and I need to figure out how to set that up. |
| 20:01 | <@Derakon> | If I just wanted to make minimal changes to this setup, then I could hand each object to the quadtree in turn, and collide it against any other nearby objects. |
| 20:02 | <@Derakon> | This would involve a lot of diving into the quadtree; once for each object. Not so great. |
| 20:03 | <@Derakon> | Alternatively, I can do collision detection as I run down the quadtree, which is only a single traversal, but would require reworking this code at least a bit. |
| 20:05 | <@gnolam> | Go with the latter. Collision detection really is best handled outside an object's own updating routines. |
| 20:05 | <@Derakon> | Part of the trick here is that preCollisionUpdate un-sets some state that postCollisionUpdate provisionally restores depending on the results of collision detection. |
| 20:05 | <@Derakon> | Things like whether or not the object is grounded. |
| 20:07 | <@gnolam> | There are several good reasons to handle collision detection separately. |
| 20:07 | <@Derakon> | Yeah, I know...I'm just griping. |
| 20:08 | <@gnolam> | For one thing, it's often desirable to check all collisions simultaneously, both for consistency of results and efficiency (as soon as an object moves, you have to re-check for collisions). |
| 20:09 | <@gnolam> | Another is that you still need to keep track of which objects have been checked for collision against other objects, again for efficiency's sake. |
| 20:10 | <@gnolam> | +which |
| 20:15 | < Rhamphoryncus> | I've always liked the idea of setting up each object's motion/velocity, then acting on it using a separate pass. Mostly from a concurrency PoV though |
| 20:16 | <@gnolam> | And with the rise of physics middleware, it is how it's done nowadays. |
| 20:16 | < Rhamphoryncus> | huh |
| 20:17 | <@Derakon> | Sadly, to my knowledge Python is singlethreaded. |
| 20:17 | < Rhamphoryncus> | CPython, yeah |
| 20:17 | < Rhamphoryncus> | mostly 'cause my work ethic sucks :P |
| 20:18 | | * Rhamphoryncus has schemes for fixing it |
| 20:18 | <@Derakon> | I hadn't realized you were working on it. |
| 20:20 | < Rhamphoryncus> | heh yeah. I did the python-safethread project, which was a heavy modification of CPython. Developed a good scalable model, but couldn't get the GC to scale sufficiently (using the refcount API) |
| 20:20 | < Rhamphoryncus> | that was followed by my attempt at statically analyzing python code, so it can be compiled.. that's floundered due to said work ethic |
| 20:20 | <@Derakon> | So how's this then? Do a first pass through all active objects to run AI updates and so on. Then hand things off to the quadtree to do object-object collision. Then do a pass through all objects to check them against terrain and let them clean up after collision. |
| 20:21 | <@Derakon> | Basically the first pass would do lines 2-7 of that pasted code, then the quadtree would do object-object collisions, then the second pass would do checkTerrain (except that it'd be done from outside the object) and tell it to do lines 9-10. |
| 20:22 | <@Derakon> | Refcount garbage collectors make me sad, largely because of some annoying work I had to do once in PHP with objects with circular references that were generated by a framework we were using. |
| 20:23 | <@Derakon> | Which isn't to say that I have a good suggestion for what to replace them with. GC is nasty business. |
| 20:23 | <@gnolam> | It always is. Even in real life. ;) |
| 20:23 | <@Derakon> | Heh. |
| 20:23 | < Rhamphoryncus> | My only concern is the corner cases. ie. can an object-object collision push an object far enough past terrain to bump to the other side? Is there a case where it gives up and overlaps the objects? |
| 20:24 | <@ToxicFrog> | Derakon: mark and sweep? |
| 20:24 | < Rhamphoryncus> | CPython uses both refcounting and tracing actually. Unfortunately the tracing can only find cycles, the rest is all refcounting |
| 20:24 | <@Derakon> | Rhamphoryncus: my assumption is that object-object collisions can set velocities, do damage, etc. but won't actually move objects around. |
| 20:24 | <@Derakon> | I.e. at the end of an object-object collision, the two objects are still intersecting. |
| 20:25 | < Rhamphoryncus> | With a new implementation I'd have no problem doing an acceptable GC |
| 20:25 | < Rhamphoryncus> | what does the movement then? |
| 20:27 | <@Derakon> | Rhamphoryncus: Line 7 of http://paste.ubuntu.com/242390/ :) |
| 20:27 | | * Rhamphoryncus wonders if multi-object collision is one of those impossible physics problems |
| 20:27 | <@Derakon> | That, and reaction to colliding with terrain, which pushes the object out of intersection. |
| 20:28 | < Rhamphoryncus> | So the object moves into the other object, then on the next turn it reacts to it? |
| 20:28 | <@Derakon> | Something like that. I could always move the point at which velocity is added to location. |
| 20:30 | < Rhamphoryncus> | eh I see no magic solution here |
| 20:30 | <@Derakon> | AI (influences velocity); precollision setup; hit objects; hit terrain; postcollision teardown; loc += vel. |
| 20:32 | < Rhamphoryncus> | imagine 2 objects heading right and one heading west, all colliding simultaneously. What's supposed to happen? |
| 20:33 | <@Derakon> | You mean like, two objects one above the other heading right, one object heading left hitting between the two? |
| 20:33 | | * TheWatcher upgrades his bugzilla, eyes the new Gigantobutton front page, WTFs |
| 20:33 | < Rhamphoryncus> | no, in line |
| 20:34 | <@Derakon> | Ahh, like the executive toy. |
| 20:34 | < Rhamphoryncus> | heh |
| 20:34 | <@Derakon> | What happens is going to depend on what order they're compared in. |
| 20:34 | < Rhamphoryncus> | yeah |
| 20:35 | <@Derakon> | But most likely one of those is the player and the other two are enemies. Enemies are allowed to intersect with each other, so they don't care; the player will hit one, recoil off in their "ouch" animation, and be immune to the other one due to mercy invincibility. |
| 20:35 | < Rhamphoryncus> | ahhh |
| 20:35 | < Rhamphoryncus> | and that game design is such a trope because it is a pita to get right :) |
| 20:36 | <@Derakon> | What trope? |
| 20:36 | <@Derakon> | Mercy invincibility? |
| 20:36 | < Rhamphoryncus> | all of it |
| 20:37 | <@Derakon> | Yeah, if you don't let dynamic objects intersect ever, then things get messy fast. |
| 20:37 | <@Derakon> | Since you have to solve rigid body problems, basically. |
| 20:37 | < Rhamphoryncus> | enemies don't collide with each other, there's only one player |
| 20:37 | < Rhamphoryncus> | Your collision isn't really one anyway. It's more of a touch attack |
| 20:38 | <@Derakon> | In this case, yeah. |
| 20:38 | < Rhamphoryncus> | umm... are you doing collision tests for all those enemies, even though they don't do anything with it? |
| 20:38 | <@Derakon> | Some grouping will let me skip the expensive tests. |
| 20:38 | <@Derakon> | Each creature gets a "group" field, and if they match then you don't do collision tests. |
| 20:40 | < Rhamphoryncus> | I wouldn't even do that. I'd put the player in a set and check the set |
| 20:40 | <@Derakon> | Well, what happens when the player fires a projectile? |
| 20:40 | <@Derakon> | (Or for that matter, the temporary objects created when the player makes a melee attack?) |
| 20:40 | < Rhamphoryncus> | their projectiles are in that set |
| 20:41 | <@Derakon> | Wait...so what do you mean by "check the set" then? |
| 20:42 | < Rhamphoryncus> | I mean if you have a thousand enemies, but the player+projectiles is only 5, check those 5 against whatever's around them. Don't iterate over everything and filter them out |
| 20:42 | <@Derakon> | Oh gods no. |
| 20:42 | <@Derakon> | That's what the quadtree is for: broadphase pruning. |
| 20:42 | <@Derakon> | Having an implicit grouping system, though, would be a bit limiting, I think. |
| 20:43 | <@Derakon> | And adding the code to do filtering on a per-pair level is straightforward. |
| 20:45 | < Rhamphoryncus> | So you mark the quadtrees based on how many player entities they have? |
| 20:46 | <@Derakon> | Er... |
| 20:46 | <@Derakon> | I would like to leave open the possibility for multiple enemy "factions". |
| 20:46 | <@Derakon> | So I can have e.g. spiders that pounce on insects or creatures getting hit by stray shots. |
| 20:46 | < Rhamphoryncus> | ahhhh |
| 20:47 | < Rhamphoryncus> | right then. Ignore everything I said :D |
| 20:47 | <@Derakon> | :) |
| 20:47 | <@Derakon> | It'll require some thought, in any event. |
| 20:49 | <@Consul> | I have no idea what either of you said. |
| 20:51 | | * TheWatcher fixes up a few more bugzilla things, goes back to documenting Tardis. |
| 20:51 | < Rhamphoryncus> | Consul: do you know what a quad tree is? |
| 20:51 | <@Consul> | No, though I might if it were described to me. |
| 20:52 | <@Derakon> | It's a spacial partitioning data structure. |
| 20:52 | <@Consul> | But it's not a big deal. I was just trying to be humurous anyway. |
| 20:52 | < Rhamphoryncus> | take a piece of paper, draw a square |
| 20:52 | <@Derakon> | Take a large 2D area. Divide it into four quads. |
| 20:52 | <@Derakon> | Take those quads, and divide them into quads. Et cetera. |
| 20:52 | < Rhamphoryncus> | now draw two lines, so you have four squares |
| 20:52 | <@Consul> | Ah, wait a minute... |
| 20:52 | < Rhamphoryncus> | draw two more lines in each, repeat ad nauseum |
| 20:52 | <@Consul> | This is how the light gun on the old Duck Hunt game worked. |
| 20:52 | <@Derakon> | No, not really. |
| 20:52 | <@Vornicus> | No, Duck Hunt used light levels. |
| 20:53 | <@Consul> | Hrm |
| 20:53 | <@Derakon> | Take a penny, drop it into the area. Find which highest-level quad it fits into without crossing any lines. Stick it there. |
| 20:53 | <@Derakon> | Drop 100 pennies onto the area. Now there's too many to reasonably put them all at the top level, so you start pushing them down into deeper quads. |
| 20:53 | <@Derakon> | Any pennies that cross lines at the top level still have to go at the top of the tree, though. |
| 20:54 | < Rhamphoryncus> | I've wondered how you deal with borders |
| 20:54 | <@Consul> | I thought the idea was the screen scanned with white blocks until the gun told the console "okay, I see white now." |
| 20:54 | <@Derakon> | Consul: when you shoot, the screen flashes different colors for each duck and for the background. The gun tells the screen what it saw. |
| 20:54 | <@Derakon> | The screen then knows what, if anything, was hit. |
| 20:56 | < Rhamphoryncus> | So the background is presumably white |
| 20:56 | <@Consul> | So, a quad tree is one of those data structures I keep hearing so much about, then? |
| 20:56 | < Rhamphoryncus> | Consul: and octrees, the 3d version |
| 20:56 | <@Derakon> | Depends on how much time you spend around developers of 2D games. :) |
| 20:57 | <@Derakon> | Quadtrees do a reasonably good job of solving the "How do I find objects near this location without iterating over every object in the system" problem. |
| 20:58 | < Rhamphoryncus> | otoh, many games simply delete objects that are far from the screen |
| 20:59 | <@Derakon> | Which I'll also be doing~ |
| 21:00 | <@Vornicus> | Which is why in many games, baddies come back if they and their spawn location leave the screen. |
| 21:01 | <@Derakon> | Ninja Gaiden 1 for the NES is notorious for this. |
| 21:01 | <@Derakon> | Sometimes you can walk an enemy's spawn location onto the screen, then they'll back off the screen and be deleted. |
| 21:01 | < Rhamphoryncus> | naw, that's because they don't track if they got killed |
| 21:01 | <@Derakon> | Other times, an enemy rushes you, you get knocked back, you move forward, and he reappears and rushes you again! |
| 21:01 | < Rhamphoryncus> | heh |
| 21:58 | <@Consul> | Okay, I think I had an epiphane while in the car on the bun run (I ran to the store for hamburger and hot dog buns)... |
| 21:58 | <@Consul> | If you split the screen into quarters... |
| 21:58 | <@Consul> | And each quarter into quarters... |
| 21:58 | <@Consul> | And so on... |
| 21:59 | <@McMartin> | That's called a "quadtree" |
| 21:59 | <@McMartin> | It's awesome for 2d collision detection |
| 21:59 | <@Consul> | Is the idea, then, that you can query an entire quarter of the screen for an object, and if it says "no", you've just saved querying lots of individual pieces. Is that the idea? |
| 21:59 | <@Derakon> | More or less. |
| 21:59 | <@Consul> | McMartin: We were discussing this earlier. |
| 22:00 | <@Derakon> | Say I want to know which objects intersect a given rectangle. |
| 22:00 | <@McMartin> | Aha. |
| 22:00 | <@McMartin> | Yeah, for something like this, quadtree is probably the way to go, but there are ways of using it like an index I don't recall offhand. |
| 22:00 | <@Derakon> | I ask the root node "What objects do you have that intersect this rectangle?" It goes through its list and does a rect collision test for each of them. It then checks which of its children intersect that rectangle, and recurses on just those children. |
| 22:00 | <@Derakon> | Repeat until you have a full list. |
| 22:07 | <@Consul> | Wikipedia's illustration looks kinda like a game of Qix. |
| 23:10 | | AnnoDomini [AnnoDomini@Nightstar-29640.neoplus.adsl.tpnet.pl] has quit [Quit: Faerie gold... it is always illusion in the end.] |
| 23:46 | | * Derakon whips together a quick Perl script to turn an ASCII map into HTML like this: http://derakon.dyndns.org/~chriswei/games/hour/map.html |
| 23:48 | <@McMartin> | Cute. |
| 23:48 | <@McMartin> | "hour"? |
| 23:48 | <@Derakon> | An Hour to Kill. |
| 23:48 | <@McMartin> | Right |
| 23:48 | <@Derakon> | My Kill Doctor Lucky-inspired deathmatch boardgame. |
| 23:48 | <@McMartin> | I recall it. |
| 23:48 | <@Derakon> | Target playtime: 1 hour~ |
| 23:48 | <@McMartin> | (You should really take a look at Frag too) |
| 23:48 | <@Derakon> | I should! |
| 23:50 | <@Derakon> | Have you ever played it? |
| 23:50 | <@McMartin> | Once or twice. |
| 23:51 | <@McMartin> | There are a few similarities but you've already designed yourself into Not A Clone |
| 23:51 | <@McMartin> | At this point you can read it for inspiration~ |
| 23:51 | | * Derakon nods. |
| 23:52 | <@McMartin> | (In particular, IIRC Frag has no equivalent of Blatancy.) |
| 23:52 | <@Derakon> | I really hope that I can make that mechanic work out. |
| 23:53 | <@Derakon> | My main concern is the fact that while *characters* don't know where each other are, *players* do. |
| 23:54 | <@Derakon> | And setting things up so that there is legitimate strategy to how you move, so it isn't just "Oh, good, I drew the card that lets me move in a way that my opponent couldn't possibly forsee, so I get to make a stealthy attack for once". |
| 23:54 | <@McMartin> | You might be able to get around that by tweaking movement rates? |
| 23:54 | <@McMartin> | yeah |
| 23:54 | <@Derakon> | That will help some, certainly. |
| 23:54 | <@Derakon> | On the flipside, the game's meant to be fast and fairly simple. |
| 23:56 | <@McMartin> | He map design would lend itself to "when you are in a position where you can't be surprised, you can't be doing much of use either." |
| --- Log closed Sun Aug 02 00:00:51 2009 |