| --- Log opened Thu Mar 15 00:00:50 2007 |
| --- Day changed Thu Mar 15 2007 |
| 00:00 | | ReivClass is now known as Reiver |
| 00:12 | < Derakon> | Aaand the first Supox I run into just happens to be carrying the broken Ultron. |
| 00:13 | <@McMartin> | Convenient, isn't it? |
| 00:13 | < Derakon> | Indeed. |
| 00:15 | < Derakon> | ...the starmap needs a "find system" mode, so I can figure out where the frick Betelgeuse is. |
| 00:15 | <@Vornicus> | It has one. |
| 00:16 | <@Vornicus> | press slash, type what you want. |
| 00:16 | < Derakon> | Ahhhh. |
| 00:16 | < Derakon> | That, um, blends in with the Kzer-za borders. ¬.¬ |
| 00:17 | < Derakon> | Anyway, time to bamboozle the Druuge. |
| 00:17 | <@Vornicus> | It is a worthy pastime. |
| 00:17 | <@McMartin> | Burn him in the atomic flames! |
| 00:17 | < Derakon> | I don't need anything from them, right? |
| 00:17 | <@McMartin> | Uh, you already got the Rosy Sphere, right? |
| 00:18 | < Derakon> | Oh, right. Um, no. |
| 00:18 | < Derakon> | Need another trade good...hrm. |
| 00:18 | < Derakon> | Deep Child fragments do? |
| 00:18 | <@McMartin> | Egg Case Fragments. |
| 00:19 | | BlueTiger [~BlueTiger@Nightstar-567.natsoe.res.rr.com] has quit [Quit: ] |
| 00:29 | | * Derakon vanishes for unspecified, ominous reasons. |
| 00:29 | | Derakon is now known as Derakon[AFK] |
| 00:31 | < Reiver> | PC2 RAM is DDR RAM, right? |
| 00:34 | | MyCatHungers is now known as MyCatVerbs |
| 00:43 | | gnolam [Lenin@Nightstar-13557.8.5.253.se.wasadata.net] has quit [Quit: Z?] |
| 00:44 | <@ToxicFrog> | Reiver: never have I heard "PC2" |
| 00:44 | <@ToxicFrog> | There's PC133, which is 133MHz SDR; and then there's DDR and DDR2. |
| 00:45 | <@McMartin> | (I can see the future in your RAM!) |
| 00:45 | <@McMartin> | (That said, these days I associate the Obnoxious DDR Announcer with his first job for Konami) |
| 00:45 | <@McMartin> | (Which was Gradius IV) |
| 00:45 | <@McMartin> | (He used the same voice in it. But then it was all lines like "DESTROY THEM ALL!") |
| 00:50 | | Thaqui [~Thaqui@Nightstar-12370.jetstream.xtra.co.nz] has joined #code |
| 01:56 | <@Vornicus> | If it weren't for the whole "quarter million distinct polys" thing I would just ask gs to generate the polys to feed into PIL. |
| 02:13 | <@ToxicFrog> | PIL? |
| 02:13 | <@Vornicus> | Python Imaging Library |
| 02:16 | | * ToxicFrog kills C++ in the face for not having classes as first-class values |
| 02:24 | | Chalcedon [~Chalceon@Nightstar-869.bitstream.orcon.net.nz] has quit [Ping Timeout] |
| 02:25 | | Chalcedon [~Chalceon@Nightstar-869.bitstream.orcon.net.nz] has joined #code |
| 02:25 | | mode/#code [+o Chalcedon] by ChanServ |
| 02:48 | | Derakon[AFK] is now known as Derakon |
| 02:49 | | * Derakon returns from karate. |
| 03:19 | | * Derakon points, laughs at the Mycon. |
| 03:33 | < Derakon> | "We are the Ethics Police. Justify that costume...Immediately!" |
| 03:34 | < Derakon> | "What I need right now, is a Touch-o-Vision." |
| 03:49 | | Thaqui [~Thaqui@Nightstar-12370.jetstream.xtra.co.nz] has quit [Quit: This computer has gone to sleep] |
| 03:54 | < Derakon> | Okay, so I have a program that will take in a PNG file and output a 0 for each fully-transparent pixel and a 1 for each partially-to-completely-opaque pixel (i.e. it makes text-based bitmaps). That's 39k for a 200x200 frame. Seems a tad excessive. |
| 03:54 | < Derakon> | Is it worth using a binary format for this, though? |
| 03:55 | | SleepingSoldier [Rob@Nightstar-4168.pools.arcor-ip.net] has left #code [] |
| 03:56 | <@Vornicus> | I think using a 1-bit setup might work |
| 03:56 | | BlueTiger [BlueTiger@Nightstar-567.natsoe.res.rr.com] has joined #Code |
| 03:56 | < Derakon> | It'd work, but decoding it would involve parsing binary files, which is mildly irritating. |
| 03:57 | <@Vornicus> | what madness are you up against anyway? |
| 03:57 | < Derakon> | Enfeh? |
| 03:57 | <@Vornicus> | Why are you doing this? |
| 03:57 | < Derakon> | I need bitmasks for collision detection purposes. |
| 03:57 | < Derakon> | And while I could spontaneously generate them when I load the frames, that would slow down loading significantly. |
| 03:58 | <@Vornicus> | Oh. YOu can generate them from the original files easily enough; you're looking at a really really simple color filter. |
| 03:58 | < Derakon> | That's how I'm generating the bitmasks, Vorn... |
| 03:58 | <@Vornicus> | I mean, on the fly. It's not /that/ hard. |
| 03:59 | < Derakon> | Well, we'll see how it affects loadtimes. |
| 04:01 | <@Vornicus> | anyway 200x200 is a 40,000 thing, and so we're looking at 80,000 indexes, 40,000 compares, and 40,000 writes. if that's not dirt cheap I don't know what is. |
| 04:01 | < Derakon> | There's 72 frames for just the one ship, all 200x200. |
| 04:01 | <@Vornicus> | Well okay that's a bit more expensive. |
| 04:02 | <@Vornicus> | Alternatively you could use the live image to do collision detection right then and there. |
| 04:02 | <@ToxicFrog> | It's still less than 20 million instructions. |
| 04:02 | <@ToxicFrog> | For all 72 frames. |
| 04:07 | | You're now known as TheWatcher |
| 04:07 | < Derakon> | Okay, that didn't take too long. Now I just have to use that info I've generated. |
| 04:11 | <@ToxicFrog> | The way I handled this last time I was writing a similar game was to give all ships shields. ?? |
| 04:11 | <@ToxicFrog> | This makes them circular and thus collision detection is a simple distance check. |
| 04:11 | < Derakon> | Oh, ships'll have shields. Shields that can be depleted, until only armor is left. |
| 04:11 | | MyCatVerbs is now known as MyCatBreaksHisComputer |
| 04:11 | <@ToxicFrog> | No armour in this game; shields go down -> instant death. |
| 04:12 | < Derakon> | EV has armor, so I must as well. |
| 04:12 | < Derakon> | What I'm creating here must be at least as capable as EV is, or else it'll be impossible for people to port previous content to it. |
| 04:13 | <@ToxicFrog> | Right. |
| 04:13 | <@ToxicFrog> | And EV does edge-level, as opposed to bounding-box, collision detection? |
| 04:13 | < Derakon> | EV, I'll note, uses pre-baked bitmasks. |
| 04:14 | < Derakon> | You provide it with a grid of all the frames of your ship, then you provide the same grid in black and white, basically. |
| 04:14 | <@ToxicFrog> | Aah. |
| 04:14 | <@ToxicFrog> | So, yes. |
| 04:14 | <@Vornicus> | It also uses those masks for transparency. |
| 04:15 | < Derakon> | I've already improved on that by letting each frame be its own distinct file; they're simply loaded in the order that ftw gives them to me. |
| 04:15 | < Derakon> | So now I'm trying to make the bitmask part easy. |
| 04:15 | <@Vornicus> | (in EVC and EVO it was possible, at least in double-speed mode, to shoot /through/ fighters) |
| 04:16 | | ReivClass [~reiver@Nightstar-2073.ubs-dsl.xnet.co.nz] has joined #Code |
| 04:16 | < Derakon> | Yes, EV has the standard high-speed teleportation problems. |
| 04:17 | < Derakon> | I'm not planning on fixing that immediately. I want to keep collision detection simple this time around. ¬.¬ |
| 04:17 | | Reiver [~reiver@IRCop.Nightstar.Net] has quit [Ping Timeout] |
| 04:18 | | ReivClass is now known as Reiver |
| 04:20 | | Forjeh [~Forj@Nightstar-869.bitstream.orcon.net.nz] has joined #code |
| 04:21 | | Forj [~Forj@Nightstar-869.bitstream.orcon.net.nz] has quit [Ping Timeout] |
| 04:25 | | BlueTiger [BlueTiger@Nightstar-567.natsoe.res.rr.com] has quit [Quit: ] |
| 04:31 | < Derakon> | I love it when I discover that I've already written the utility function I need. |
| 04:43 | < Derakon> | Well, bitmask collision detection appears to work now. Woot. |
| 04:43 | <@Vornicus> | woot |
| 04:43 | < Derakon> | Surprisingly painless, all things considered. |
| 04:44 | < Derakon> | My biggest bug was failing to remember that I have two constructors, and I'd only added the bitmask-generation code to one of them. |
| 04:44 | < Derakon> | Man, I love name-based maps. |
| 04:45 | < Derakon> | I just tell Lua "The objects named "foo" and "bar" collided; do what you like." And Lua looks up foo and bar and says "Hey, you shmucks; you ran into each other. Be more careful next time." |
| 04:47 | <@ToxicFrog> | 'name-based maps'? |
| 04:47 | < Derakon> | Maps of strings to objects. |
| 04:48 | <@ToxicFrog> | Aah. |
| 04:48 | <@ToxicFrog> | Delicious introspection. |
| 04:48 | < Derakon> | When you tell the engine to create an object, you give that object a name, which is unique. The engine makes a map of names to objects. So do you (where you is Lua). |
| 04:52 | < Derakon> | Anyway, I have Lua classes; I have keyboard input; I have collision detection. Next step is to code up a combat AI. Whee! |
| 05:07 | | AnnoDomini [~farkoff@Nightstar-28991.neoplus.adsl.tpnet.pl] has joined #Code |
| 05:27 | | Derakon is now known as Derakon[AFK] |
| 05:39 | | You're now known as TheWatcher[T-2] |
| 05:40 | | MyCatBreaksHisComputer is now known as MyCatVerbs |
| 05:41 | | You're now known as TheWatcher[afk] |
| 06:40 | | Zombor [~wandering@Nightstar-15114.dsl1.nor.ny.frontiernet.net] has joined #Code |
| 06:45 | | Zombor [~wandering@Nightstar-15114.dsl1.nor.ny.frontiernet.net] has left #Code [] |
| 06:52 | | Vornicus is now known as Vornicus-Latens |
| 07:03 | | Forgles [~Forj@Nightstar-869.bitstream.orcon.net.nz] has joined #code |
| 07:04 | | Forjeh [~Forj@Nightstar-869.bitstream.orcon.net.nz] has quit [Ping Timeout] |
| 07:42 | | Thaqui [~Thaqui@Nightstar-12370.jetstream.xtra.co.nz] has joined #code |
| 07:45 | | MahalWork is now known as Mahal |
| 07:51 | | Chalcedon [~Chalceon@Nightstar-869.bitstream.orcon.net.nz] has quit [Quit: ] |
| 08:20 | | Forgles [~Forj@Nightstar-869.bitstream.orcon.net.nz] has quit [Ping Timeout] |
| 10:24 | | fr0st [~fr0st@80.83.238.ns-13499] has joined #Code |
| 10:25 | < fr0st> | hi all from russia |
| 10:26 | | * fr0st has twitched Raif |
| 10:26 | | * fr0st has twitched Derakon[AFK] |
| 10:26 | | * fr0st has twitched EvilDarkLord |
| 10:26 | < fr0st> | HELLO |
| 10:26 | < fr0st> | i love php & mysql |
| 10:27 | | fr0st [~fr0st@80.83.238.ns-13499] has quit [Quit: В движение счастье моё, в непостоянстве жизнь] |
| 10:45 | | bx [~zcxzxxc@Nightstar-1221.alshamil.net.ae] has joined #Code |
| 10:52 | | bx [~zcxzxxc@Nightstar-1221.alshamil.net.ae] has left #Code [] |
| 10:53 | | Pi [~sysop@Nightstar-6915.hsd1.or.comcast.net] has quit [Ping Timeout] |
| 11:10 | | * Reiver tries to decide as to the merits of a 4200+ vs a 3600+ CPU. |
| 11:11 | < Reiver> | The first is almost 50% more expensive than the latter. At the same time, I probably won't by another later. |
| 11:19 | | Thaqui [~Thaqui@Nightstar-12370.jetstream.xtra.co.nz] has quit [Quit: This computer has gone to sleep] |
| 11:21 | | Thaqui [~Thaqui@Nightstar-12370.jetstream.xtra.co.nz] has joined #code |
| 11:44 | | KarmaBot [~karma.bot@Nightstar-28991.neoplus.adsl.tpnet.pl] has joined #Code |
| 11:44 | < Reiver> | !4200/3600 |
| 11:44 | < KarmaBot> | [Reiver] 4200/3600 = 1.166667. |
| 11:44 | < Reiver> | !3600/4200 |
| 11:44 | < KarmaBot> | [Reiver] 3600/4200 = 0.857143. |
| 11:44 | < Reiver> | hrm. |
| 11:54 | < Reiver> | Athlon 64 X2 4400+ Athlon 64 X2 3600+ Athlon 64 X2 4200+ |
| 11:54 | < Reiver> | $316.85 $180.52 $296.20 |
| 11:55 | | * Reiver tries to decide. If one goes up, one may as well go /right/ up, almost. ...But whether or not it's worth that price jump is another matter. |
| 11:57 | < Reiver> | !3600/4400 |
| 11:57 | < KarmaBot> | [Reiver] 3600/4400 = 0.818182. |
| 12:12 | | Reiver is now known as ReivZzz |
| 12:26 | | gnolam [Lenin@Nightstar-13557.8.5.253.se.wasadata.net] has joined #Code |
| 13:21 | <@ToxicFrog> | !4400/316 |
| 13:21 | < KarmaBot> | [ToxicFrog] 4400/316 = 13.924051. |
| 13:21 | <@ToxicFrog> | !3600/180 |
| 13:21 | < KarmaBot> | [ToxicFrog] 3600/180 = 20. |
| 13:21 | <@ToxicFrog> | !4200/296 |
| 13:21 | < KarmaBot> | [ToxicFrog] 4200/296 = 14.189189. |
| 13:21 | <@ToxicFrog> | The 3600 is definitely the best value for money. |
| 13:41 | | Thaqui [~Thaqui@Nightstar-12370.jetstream.xtra.co.nz] has left #code [Leaving] |
| 14:06 | | Derakon[AFK] [~Derakon@Nightstar-12737.sea2.cablespeed.com] has quit [Connection reset by peer] |
| 14:39 | | Netsplit DeepThought.NY.US.Nightstar.Net <-> Blargh.CA.US.Nightstar.Net quits: Serah, ReivZzz |
| 14:41 | | gnolam [Lenin@Nightstar-13557.8.5.253.se.wasadata.net] has quit [Quit: Reboot.] |
| 14:42 | | Serah [~Z@87.72.36.ns-26407] has joined #Code |
| 14:43 | | gnolam [Lenin@Nightstar-13557.8.5.253.se.wasadata.net] has joined #Code |
| 14:45 | | ReivZzz [~reiver@IRCop.Nightstar.Net] has joined #Code |
| 14:45 | <@ToxicFrog> | augh, get out of my heaaaaaaad |
| 14:46 | <@ToxicFrog> | I keep on wanting to remake StarCraft in the supcomm engine |
| 14:49 | | Netsplit DeepThought.NY.US.Nightstar.Net <-> Blargh.CA.US.Nightstar.Net quits: ReivZzz |
| 15:10 | | gnolam [Lenin@Nightstar-13557.8.5.253.se.wasadata.net] has quit [Ping Timeout] |
| 15:49 | | gnolam [Lenin@Nightstar-13557.8.5.253.se.wasadata.net] has joined #Code |
| 15:56 | <@Vornicus-Latens> | heh |
| 16:00 | | Vornicus-Latens is now known as Vornicus |
| 16:01 | <@ToxicFrog> | I'm pretty sure it could be done, too. |
| 16:03 | <@Vornicus> | so am I. |
| 16:04 | <@Vornicus> | Last night I found myself wondering, apropos of nothing, what the hardest Starcraft effect to create would be. I think it's either the Creep, the Nydus Canal, or one of the Arbiter abilities. |
| 16:05 | <@ToxicFrog> | The Nydus Canal we already have code for. |
| 16:08 | <@Vornicus> | Do things know how to path through a Nydus Canal? |
| 16:09 | <@ToxicFrog> | No. |
| 16:09 | <@Vornicus> | cuz man that's an effect I always wanted |
| 16:09 | <@ToxicFrog> | Although it might be possible to add that. |
| 16:10 | <@ToxicFrog> | As for the Arbiter abilities...it has, what, passive cloaking, Recall, Stasis, am I forgetting an ability? |
| 16:10 | <@ToxicFrog> | Cloaking we can do as jamming easily and can probably do as actual cloaking. Recall, again, we already have code for. |
| 16:10 | <@Vornicus> | That's all three. |
| 16:11 | <@ToxicFrog> | Stasis is also easy, I think. |
| 16:11 | <@EvilDarkLord> | What be this thing you're planning? |
| 16:11 | <@Vornicus> | the thing about Cloaking is that it doesn't work on the Arbiter itself. |
| 16:11 | <@ToxicFrog> | Creep is the only one I can't immediately think of how to do. |
| 16:11 | <@ToxicFrog> | EvilDarkLord: <ToxicFrog> I keep on wanting to remake StarCraft in the supcomm engine |
| 16:11 | <@Vornicus> | And Stasised units can't get damaged or affected by special effects. |
| 16:12 | <@ToxicFrog> | Yes. |
| 16:13 | <@ToxicFrog> | I can think of at least two ways to implement that, the right way and the easy way. |
| 16:14 | <@Vornicus> | The crappy thing about stasis in original Starcraft was that if you asked for a team with some of its members in stasis, the stasis'd members would become permanently removed from the team. |
| 16:16 | <@ToxicFrog> | Yeah. |
| 16:16 | <@ToxicFrog> | The easy way is to move the units in stasis into orbit and replace them with inert objects. |
| 16:16 | <@ToxicFrog> | (after disabling their ability to move) |
| 16:16 | <@ToxicFrog> | Then move them back when the stasis wears off. |
| 16:17 | <@Vornicus> | ...would you want to allow creatures to use special abilities automatically? |
| 16:22 | <@ToxicFrog> | Make it an option. |
| 16:22 | <@ToxicFrog> | Which, again, we already have code for. Right-click toggles autofoo. |
| 16:22 | | * Vornicus ponders |
| 16:23 | <@Vornicus> | I'd want some creatures to do it - BCs should fire on strong targets with the Yamato cannon, for instance, but stimpacks should only get done by hand. |
| 16:24 | <@EvilDarkLord> | Is this a copy of the original SC or will you include BW units? |
| 16:25 | <@EvilDarkLord> | (Since if medics are present it might make sense to auto-stimpack) |
| 16:25 | <@Vornicus> | ooh, complex cyborg AI. |
| 16:27 | <@Vornicus> | Speaking of medics, what about optic flare? |
| 16:27 | <@ToxicFrog> | EvilDarkLord: it's never going to be implemented, at least not by me. |
| 16:27 | <@Vornicus> | easy? |
| 16:27 | <@ToxicFrog> | Vornicus: easy. Disable omni, reduce vision radius. |
| 16:28 | <@ToxicFrog> | EvilDarkLord: if I were going to implement it, however, it would include SCBW. |
| 16:28 | <@Vornicus> | there's an omni button? |
| 16:28 | <@ToxicFrog> | Vornicus: oh, right, you don't have it. |
| 16:28 | <@ToxicFrog> | Sensors come in three flavours - radar, sonar, and omni. |
| 16:28 | <@Vornicus> | aha |
| 16:29 | <@ToxicFrog> | Omni detects cloaked and stealthed units within range, as well as un-detecting sensor ghosts generated by ECM. |
| 16:29 | <@Vornicus> | Omni is just Detector, then. |
| 16:29 | <@ToxicFrog> | Yes. |
| 16:31 | | * Vornicus wanders around his hard drive, finds something he forgot he did - some screenshot maps of Metroid Fusion. |
| 16:31 | | Pi [~sysop@Nightstar-23945.hsd1.wa.comcast.net] has joined #code |
| 16:31 | | mode/#code [+o Pi] by ChanServ |
| 16:33 | <@ToxicFrog> | The things that I think would give the most trouble: building addons, flying buildings, discrete resource harvesting, Creep. |
| 16:38 | <@Vornicus> | ...okay yeah I didn't think of those. |
| 16:42 | <@ToxicFrog> | (discrete resource usage might be a problem, but as far as I'm concerned it can die in a fire, so) |
| 16:46 | | * Vornicus fiddles with polygon scan conversion. |
| 16:47 | <@Vornicus> | okay. I need to make it so half the lines that go through a center point of a pixel don't count as containing that pixel. |
| 16:50 | <@Vornicus> | ...since lines have an order in which they go through points, I can merely say "if left.y > right.y or left.y == right.y and left.x > right.x" |
| 16:52 | | SleepingSoldier [~Rob@Nightstar-4242.pools.arcor-ip.net] has joined #code |
| 16:52 | | SleepingSoldier is now known as GeekSoldier |
| 17:22 | | * Vornicus fiddles. |
| 17:22 | | gnolam is now known as Rome |
| 17:22 | | * Rome burns. |
| 17:22 | | Rome is now known as gnolam |
| 18:26 | | * Vornicus fiddles with polygon insideness testing. |
| 19:11 | <@ToxicFrog> | From this text on first-order-logic based AI: |
| 19:11 | <@ToxicFrog> | 5. Animals with brains that are small (or below) relative to the normal brain size for their |
| 19:11 | <@ToxicFrog> | species are silly.[2] |
| 19:11 | <@ToxicFrog> | 2 |
| 19:11 | <@ToxicFrog> | It is important to remember that the goal for this knowledge base was to be consistent and useful within a world of |
| 19:11 | <@ToxicFrog> | talking stuffed animals, not to be a model of the real world. |
| 19:14 | | * jerith grins. |
| 19:18 | | GeekSoldier [~Rob@Nightstar-4242.pools.arcor-ip.net] has left #code [] |
| 20:00 | | Serah [~Z@87.72.36.ns-26407] has quit [Ping Timeout] |
| 20:01 | | Serah [~Z@87.72.36.ns-26407] has joined #Code |
| 20:07 | < MyCatVerbs> | ToxicFrog: what in the green blazes? =) |
| 20:10 | | MyCatVerbs is now known as MyCatHungers |
| 20:38 | | EvilDarkLord [~jjlehto3@Nightstar-2194.vipunen.hut.fi] has quit [Quit: AnnoDomini ] |
| 20:44 | | EvilDarkLord [~jjlehto3@Nightstar-2194.vipunen.hut.fi] has joined #code |
| 20:44 | | * Vornicus fiddles with scanline code. |
| 20:49 | | ReivZzz [~reiver@IRCop.Nightstar.Net] has joined #Code |
| 20:49 | | Chalcy [~Chalceon@Nightstar-869.bitstream.orcon.net.nz] has joined #Code |
| 20:49 | | Forj [~Forj@Nightstar-869.bitstream.orcon.net.nz] has joined #Code |
| 21:05 | | Chalcy is now known as ChalcyOut |
| 21:28 | <@ToxicFrog> | MyCatHungers: an example of how to construct a knowledge base in first-order logic from which one can reason that (Bear(Pooh) & Size(Brain(Pooh)) <= Very(Small)) -> Silly(Pooh) |
| 21:29 | <@Vornicus> | Silly old bear. |
| 21:33 | <@Vornicus> | ...and now that I look at this code it could be still simpler. |
| 21:42 | | BlueTiger [BlueTiger@Nightstar-567.natsoe.res.rr.com] has joined #Code |
| 21:46 | | MyCatHungers is now known as MyCatVerbs |
| 21:47 | < MyCatVerbs> | ToxicFrog: knowledge bases? |
| 21:47 | < MyCatVerbs> | ToxicFrog: weren't those, like, really *really fashionable about a decade back, but then it turned out that basically nobody ever actually found a use for the damn things? |
| 21:48 | <@ToxicFrog> | We may be using different definitions here. |
| 21:48 | <@McMartin> | Deductive Databases are Quite Handy, Thank You. |
| 21:48 | <@ToxicFrog> | Here, a KB is a set of axioms and rules about the world from which the agent can deduce both (a) world state and (b) optimal actions. |
| 21:49 | <@ToxicFrog> | we recently built one that plays a Hunt the Wumpus variant as an exercise. |
| 21:49 | < MyCatVerbs> | No, we're thinking of exactly the same thing here. |
| 21:49 | <@McMartin> | They can also be represented in ways that let you represent an exponential number of facts in polynomial space. |
| 21:49 | < MyCatVerbs> | I just never actually ever heard of a practical use of the things. |
| 21:50 | <@McMartin> | It never really got past research prototype level, but http://bddbddb.sf.net/ does things that were thought laughably impossible in 2003. |
| 21:50 | < MyCatVerbs> | McMartin: provided that those things happen to have the right graph structure? |
| 21:50 | | * McMartin uses it for his own program analysis work as a ground to build from. |
| 21:50 | <@McMartin> | MCV: Yes. Happily, pointer alias information tends to. |
| 21:51 | <@McMartin> | It's also a lot easier to write program analyses declaratively than as codewalkers. |
| 21:51 | | BlueTiger [BlueTiger@Nightstar-567.natsoe.res.rr.com] has quit [Quit: ] |
| 21:51 | < MyCatVerbs> | I mean that the topology has to be favourable, there has to be some depth to it to make them useful. It's not really going to be worth using on data sets where none of the relations can be followed for more than one or two nodes. |
| 21:51 | <@McMartin> | Uh, so, this is a problem domain that's been a pain in the ass for 30 years. |
| 21:52 | <@McMartin> | You asked if it was useful anywhere. |
| 21:52 | <@McMartin> | It damn near solves it entirely. |
| 21:52 | <@McMartin> | So yeah, it's still a useful technique. |
| 21:52 | <@McMartin> | Er. "This" = "exploiting pointer information", and "it" = "deductive database/KB tech" |
| 21:53 | < MyCatVerbs> | I see, thanks. Where do you harvest all the pointer information from, usually> |
| 21:53 | < MyCatVerbs> | s/>/?/ |
| 21:54 | <@McMartin> | There's been about 30 years of research in that. |
| 21:55 | <@McMartin> | But the answer is of the form "these two pointer dereferences in the code may refer to the same object", or "This is the set of heap objects to which this variable can point" |
| 21:55 | <@McMartin> | That latter is problematic due to there being a potentially infinite number of heap objects at run time, so you have to play games with naming. |
| 21:55 | < MyCatVerbs> | That sounds like a right cow. |
| 21:55 | <@McMartin> | (The former is, strictly, an "alias" analysis, and the latter a "points-to" analysis, but at the end of the day, they're the same thing.) |
| 21:56 | <@McMartin> | In any event, Binary Decision Diagrams are Really Quite Good at representing points-to information. |
| 21:56 | <@McMartin> | There was some seminal work on that at McGill, and our group automated a lot of the intervening steps. |
| 21:57 | <@McMartin> | Well, by "our group" I mean "John Whaley" |
| 21:57 | <@McMartin> | The rest of us after him gained our notoriety primarily by coming up with problems that are actually hard enough to require results that precise. |
| 21:58 | <@Vornicus> | heh |
| 21:58 | <@McMartin> | Because there's a cheapass alias analysis based on union-find that's been around for a little under 20 years now that does about as well as anything else for questions like "Do I have to reload this from memory, or can I keep it in a register?" |
| 21:58 | <@McMartin> | Not that that is an easy problem. MSVC6 by default will produce incorrect code for: |
| 21:59 | < MyCatVerbs> | So, assuming you succeed in making the problems tractable and finding simple enough ways to do things that people not living, eating and breathing graph theory can be taught them, this is all going to end up in the N+1th edition of the Turing Omnibus, with any luck. |
| 21:59 | <@McMartin> | int foo (int *a, int *b) { *a = 3; *b = 4; return *a; } |
| 21:59 | <@McMartin> | MCV: I forget whether or not I've shown off PQL in here, actually, but PQL matching is hard enough. |
| 22:00 | <@ToxicFrog> | McMartin: in what way is the code it generates incorrect? |
| 22:00 | <@McMartin> | TF: It will always return 3. |
| 22:00 | <@ToxicFrog> | Oooooops. |
| 22:00 | <@McMartin> | There's a switch to make it generate correct code in that case, but it's off by default~ |
| 22:01 | <@McMartin> | Whaley's analysis will flag that as an error if and only if there can exist a call that will return 4. |
| 22:01 | <@McMartin> | Because it actually considers an exploded call graph and treats all non-recursive functions as inlined. |
| 22:02 | <@McMartin> | And sure, that means you end up with, like, 10^80 nodes. |
| 22:02 | < MyCatVerbs> | ??? |
| 22:02 | <@McMartin> | But that's OK! |
| 22:02 | <@McMartin> | It still fits in, like, 200MB of RAM. |
| 22:02 | < MyCatVerbs> | What should that do *other* than setting a and b in the outside scope to 4 and 3 and then returning 3? |
| 22:02 | <@McMartin> | MCV: consider the call foo (&x, &x);. |
| 22:02 | <@Vornicus> | Well, it will explode if either is null, but |
| 22:03 | <@Vornicus> | that too. |
| 22:03 | <@McMartin> | If a and b are aliased, it should return 4. |
| 22:03 | < MyCatVerbs> | Ahhh, I see. Thanks. |
| 22:03 | <@McMartin> | Pointer Analysis Is Hard (tm). |
| 22:03 | <@McMartin> | This is one of the reasons C and C++ are extremely difficult to optimize safely. |
| 22:03 | < MyCatVerbs> | I've been getting that impression. |
| 22:04 | < MyCatVerbs> | Wouldn't it be easier or safer to do it in LISP? |
| 22:04 | <@McMartin> | Yes. One of the other reasons Whaley got good results is that he's targeting Java. |
| 22:04 | | * MyCatVerbs nods. |
| 22:04 | <@McMartin> | Which is even better than LISP, because in Java, not only do you have references instead of pointers, you also have strong static typing. |
| 22:04 | < MyCatVerbs> | Sensible of him. On second thoughts, Java's probably an even better language to target than LISP for this stuff. |
| 22:04 | <@McMartin> | Er. Static typing. LISP has strong typing too. |
| 22:05 | <@McMartin> | Also, Java actually gets used for stuff. |
| 22:05 | | * McMartin has been using the pointer data to construct attack vectors on Java web applications. |
| 22:05 | <@McMartin> | *cough* I mean, to perform runtime verification on Java web applications. |
| 22:06 | <@McMartin> | (Runtime Verification: What you get when you hand JUnit to formal methods dudes) |
| 22:06 | <@Vornicus> | McM: do you mean that you're going to use the pwned stamp on applets now? |
| 22:06 | <@McMartin> | I'm not really messing with applets, as those are client side. |
| 22:07 | | * MyCatVerbs facepalms. |
| 22:07 | <@McMartin> | I haven't actually found a conveniently exploitable XSS vulnerability in my test suite yet. |
| 22:07 | <@McMartin> | Of course, since in order to actually do the attack, I have to deploy the app, and most of these are J2EE monstrosities, it's easier to analyze their source code than it is to make them run. |
| 22:08 | < MyCatVerbs> | See, you just spent the last fifteen minutes explaining this to me while I sit around dumbfounded wondering what the Hell it's for. Then you point out the probably-obvious-in-retrospect fact that you can turf up incorrect algorithms with it. |
| 22:08 | < MyCatVerbs> | *exploitably incorrect, too* |
| 22:08 | <@McMartin> | Such is the nature of pure research, yes. |
| 22:08 | | * Vornicus eyes. It can't /possibly/ be this simple. |
| 22:09 | <@McMartin> | This has been going from math journals to compiler optimization journals to program analysis journals to security journals over the past decade or so. |
| 22:09 | < MyCatVerbs> | Heh. There's a nasty thought. |
| 22:09 | <@McMartin> | (You can also use it to do things like plug memory leaks.) |
| 22:10 | | BlueTiger [BlueTiger@Nightstar-567.natsoe.res.rr.com] has joined #Code |
| 22:10 | < MyCatVerbs> | It sounds like you could use it to do hardware analysis, too. |
| 22:10 | | * Vornicus is writing polygon scan conversion code. It is /absurdly simple/. |
| 22:11 | <@McMartin> | ... are you properly handling convex polys? |
| 22:11 | <@McMartin> | Because if not, yeah, it's drawing two lines. |
| 22:12 | <@McMartin> | And interpreting the results slightly differently. |
| 22:12 | <@Vornicus> | As it is, I am working with not-necessarily-simple polygons and even/odd filling. |
| 22:13 | <@McMartin> | Which is still pretty simple, but not as absurdly so. |
| 22:13 | <@Vornicus> | It is a lot simpler than I was afraid it would be. |
| 22:14 | < MyCatVerbs> | You were *afraid* it would be simple? |
| 22:15 | < MyCatVerbs> | Masochist! ;) |
| 22:15 | <@Vornicus> | I was afraid that it would be huge and hairy. |
| 22:17 | <@Vornicus> | (if I were doing a different fill method - nonzero, positive, something like that, this would be harder) |
| 22:17 | < MyCatVerbs> | Nasty Problem Domains (TM), now with added Pubic Gnarliness! |
| 22:18 | <@Vornicus> | Hrm. You know, I really like the colored parentheses thing from Excel. |
| 22:23 | | * Vornicus sets up an iterator that spews pixels one at a time from a polygon fill. |
| 22:23 | <@Vornicus> | Have I mentioned lately that I /love/ Python? |
| 22:25 | <@Vornicus> | sorted(filter(lambda x: x is not None, (scanline_crosses_edge(edge,y) for edge in self.edges()))) <--- woot. |
| 22:41 | <@McMartin> | Hm. Wouldn't it be better to blit 1-pixel-high rectangles? |
| 22:42 | <@Vornicus> | I'm iterating pixels, because I'm not blitting. |
| 22:43 | <@Vornicus> | I'm using them to choose pixels to composite into a single pixel for a map projection manipulator. |
| 22:44 | <@McMartin> | Ah. |
| 22:44 | <@McMartin> | http://worsethanfailure.com/Articles/The_Pyramid_of_Error.aspx amuses me. |
| 22:45 | <@Vornicus> | ow |
| 22:53 | <@ToxicFrog> | Vornicus: colored parentheses thing? |
| 22:54 | <@Vornicus> | Excel will color paired parentheses the same. |
| 22:54 | <@ToxicFrog> | Aah. |
| 22:54 | <@ToxicFrog> | Convenient. |
| 22:56 | <@Vornicus> | Indeed. |
| 23:01 | | Derakon [~Derakon@Nightstar-12737.sea2.cablespeed.com] has joined #code |
| 23:17 | | ReivZzz is now known as Reiver |
| 23:19 | | BlueTiger [BlueTiger@Nightstar-567.natsoe.res.rr.com] has quit [Quit: ] |
| 23:26 | | Doctor_Nick [~fdsaf@Nightstar-27777.rag-a.fsu.edu] has joined #code |
| 23:35 | | * Reiver ponders, frowns. |
| 23:35 | < Reiver> | I'm looking at CPUs. |
| 23:35 | < Reiver> | I keep wanting to buy a cheap one now, in the knowledge that I can "Get a better one later". |
| 23:36 | < Reiver> | However, if I wait till a higher-spec one drops to the price limits of the current cheap one, I'm /still/ eventually spending 2x the price on the chips in question. |
| 23:36 | < Derakon> | Just so long as by "cheap" you mean "proven but old" instead of "shoddy", you should be fine. |
| 23:36 | < Reiver> | 'cuz I paid the cheap price, twice. |
| 23:37 | < Derakon> | And yep. |
| 23:37 | < Reiver> | If I paid that money *up front*... |
| 23:37 | < Doctor_Nick> | just look for the price/performance sweetspot |
| 23:37 | < Doctor_Nick> | and buy that one |
| 23:37 | < Reiver> | ...I could get a very nice chip indeed - probably at least as fast as the 'cheap later on' chip I'd look at. |
| 23:45 | | Thaqui [~Thaqui@Nightstar-12370.jetstream.xtra.co.nz] has joined #code |
| --- Log closed Fri Mar 16 00:00:11 2007 |