_madk,

I know that everyone is telling you you'll fail, but... The truth is I think it will be a productive exercise.

One way to think of this particular entropy problem is like so:

- There *is* a random seed to go with an RNG that will convert your data to something more compressible. In fact, whatever bytes of data you want to compress will likely appear directly in your RNG stream, if it's a good enough stream and you aren't trying to compress too many bytes.

- So to compress any data, it remains to just store the seed that you use to generate that stream, and/or the stream position where that data appeared.

... however...

- The data you need to record in order to store that seed and/or it's position in the stream will eat up, on the whole, whatever benefit you gain from storing it this way. You actually will be able to compress your data this way, but not beyond a certain point.

Another simple "proof" that there are limits to compression:

- Imagine you have a compression algorithm that will always reduce the file size by 1%. I.e., there is not a theoretical limit to compression and you have an algorithm that is very modest, and will compress a file by only 1%. Further, assume it's general purpose, that it can compress anything.

- Start with any input file, and keep re-compressing your output, over and over again.

- Eventually you will have a file that is say 99 bits long (99 bits * 1% = 0 bits, if you're rounding down which we will do to support our "modest" argument; so this is as far as you can go if your algorithm always compresses by 1%)

- Now, 99 bits is a lot of bits. Not only that, but your typical file will have to have been reduced a lot of times to get it down to 99 bits. However...

There are certainly more than 2^99 different possible files! For instance, you can easily imagine creating them by brute force. But you've only got 2^99 possible compression outcomes. So your algorithm can't have compressed ANYTHING; since each of these 2^99 must eventually decompress to SOMETHING, you can imagine decompressing your possible 2^99 possible "final" compression outcomes to something.

So there must be files it doesn't know how to compress. But this conflicts with our original proposition that it's a general purpose compression algorithm. So there has to be a problem somewhere with our assumption about how our theoretical algorithm can work. Either it can't compress any type of file, or it must get to a point where it can't even reduce it by 1%.

Well, this is sort of a lacksadaisically stated version of this proof but there is a more robust version here:

http://en.wikipedia.org/wiki/Magic_compression_algorithm#Limitations

Something else that is really interesting to read up on is:

http://en.wikipedia.org/wiki/Kolmogorov_complexity

The point is, I think it's very useful learning and experimental experience to try these things out. The truth is even if you found a novel way of compressing something that wasn't actually better than what we already have, it could be quite useful. That alone would be worth experimenting. Maybe it would be useful for things other than compression, too!

But even if you don't, it's really a great exercise to wrap your head around these kind of problems-- it's what makes math so interesting! And you never know what you'll actually discover. I don't pretend to be an expert in these kind of topics but the way I see it they are quite deep and definitely worth experimenting with.

Drones

Finally comes the magic: drones. Where my preferred design differs at least a little from other designers is that my objects do not have per-frame logic. Instead, objects are essentially static, and respond only to events (such as clicking).



Drones are essentially entities that only have per-frame update logic. They are not tied to a specific object, and do not have a physical or visible representation.

Enemies are represented by drones. When we want to place for example a lizard, what I do is select the lizard object and add it to the map. Next, when the map loads it does a quick search for all objects that have a special property: "is_enemy_object". Next, it asks the object what type of enemy drone it should create, and creates that drone. Finally the drone is linked to the object itself and the object is now "drone controlled" and can attack/etc.



More on the Above Diagram
First, the green part is what I'm calling "common practice". This is the normal way to organize game logic, with everything more or less wrapped into one ball. This can work well particularly for small projects; in fact for smaller projects this is precisely what I do.

The right hand part is how Texas is structured. I have a class called "Sprite" which is fairly a misnomer. Think of it as a physics object; it exists in a physical space. Tied to it can be three types of things: first, a renderable. Renderable just defines what it looks like, for instance it could be a cube, a flower, a dresser, or a burning fire.

Also attached to a sprite is a soundable. This is (you guessed it) a sound effect generator. Since the sprite represents the physicality of the object it's fairly easy to do things like locate sound effects in 3D space, etc.

Finally there is the real magic, "mover". Mover is like a special kind of AI that knows only how to move things around. It does not animate or try to coordinate with animation, it only moves the sprite's x/y. Movers handle collisions, can do interesting things like apply gravity, and in fact can be in some cases combined together.

These four classes are in C++; they are pretty bare-bones to look at, I'd estimate only a few thousands lines all told. But they are fast, efficient and they get the core low-level work done.

Next comes Object. This is a Lua class with enormous functionality. In fact it's sort of like an overgrown version of the Object class on the left. It interacts with and in some ways defines the actual game engine. There's too much to describe here, really!

... Which brings us to the Drone class itself. As you might gather from looking at the above diagram, Drones can be really complex. In fact, there is so little "set behaviour" for a drone, they can be almost anything. Probably they would benefit for a little bit of categorization; for instance drones that are attached to the player, drones that are used for area-wide effects, and so forth. But the interface stays roughly the same and so they are just sort of lumped in together.



Global Drones, NPCs
Drones do not have to be tied to an object and they do not have to be created by an object. Moreover, they don't even have to be tied to an area!

When the game starts, it creates a list of "npc drones"; one per NPC. Right now there are 34 NPCs in the game, and *they are active at all times.* The game engine has facilities for pathfinding even on areas that aren't loaded into memory (this is a really nice trick that I'll have to explain later) so an NPC can do something along these lines:

- Suppose the NPC is in the field, farming.
- Now we notice that it's 6pm, time for dinner!
- Ask the game engine for a path from our current position to the dinner table.
- Start a counter within this path, so we know where we are in an area even if the area is not loaded.
- Each nth of a second, move to the next step.

Now, simultaneously what is going on is we are:

- Check if the area has changed since the last frame update.
- If it has, then check if the area is the same as our current path area.
- If it is, then add an object representation for us to the current area so the player can see us/talk to us.
- "Pause" the control logic above, and use a different walk algorithm to walk to our destination point in-area.
- The above is in case the player stops to talk to us, etc.;
- Once we leave the current area, the above control logic resumes

As you can see, NPC logic is fairly complex. The main trick is that we don't keep the entire world in-memory, but we want NPCs to exist globally at all times. The game really does maintain a daily schedule for all NPCs and tracks them at all times. If you follow NPCs around, you will see they get into all sorts of trouble!



Next Time: The Editor
The next part in "La Tour" will have some screenshots and an explanation of the in-game editor that I use. Stay tuned...

I totally started laughing when I read "Chicken AI"...   I'm glad to see you're still hard at work on this game!  It looks like it's coming along nicely.

Thank you! The new cutscene and AI system really is much, much nicer. I just had to rework a lot of things the past couple nights and it really was no big deal.

The thing I like about it is that it supports essentially "fuzzy programming". Like, if something isn't working with part of enemy behaviour, I don't have to pull out my hair coming up with some kind of perfect design: I can just patch that behaviour directly, quickly and without worrying that I'll break something else. Compared to hard-coding the AI it's nearly fool proof.

I don't know that Ocarina of Time really deserves that title of #1.  Counting the reviews only 7 out of 28 reviews were actually done of it within a year of it's release, with many of the reviews being up to 5 years after.  I'm pretty sure people will only go back and review a 5 year old game if they really enjoyed it, and my guess is they give it a little slack for being an older game and may not notice some of their initial gripes, and they view it as a classic, which definitely lenses the results at least a little.

Loz: Ocarina of Time might still top the charts if it were properly covered right when it came out, but it doesn't really have that great of a sample base of reviews right when it came out, so it's firm hold on the #1 spot is iffy.

Just thought I'd throw that out there.

But... the day I brought home Ocarina of Time was such an amazing moment in my life. I, personally, think it deserves that spot. I skipped a week of university classes when I got that game, hahaha!

Great memories playing OoT: I had it set up in my parents room and was playing with this girl, actually a really cute girl but we were not romantic or anything, anyhow she just liked to watch me play it. THEN my dad walks in, in his underwear. Oh my.

The All-New for 2010 Kitty Lambda 4 Part Game Dev TOUR - Part I: World Elements




La Tour Part I: World Elements

I recently got a question from a friend about the basics of how I do game development (how am I doing 3D, how does my engine work, tc.), so that seemed as good a reason as any to get back on it with my blog (this blog has been inactive for I think a month or more!)

So it begins! A four part tour of how I do game development...



World vs. Play

The way I tend to structure my games (and this is ever-changing) is as a separation between world, which is like a simulation or sandbox, and play, which describes the gameplay flow and any control issues (e.g., when the player dies, go to a gameover screen, show whatever map the player is on, etc.)

The world class is the interesting part to conceptualize. First, Texas' world is split into areas of 50x50 blocks, and at any time up to 5 areas are loaded into memory. Only one area is "current", so the other 4 are just essentially a cache to reduce loading times if you go back and forth between a few screens.



Terrain

Each area has on it a few types of things: first, there is terrain, which is a "smooth" looking mesh (but still on a 50x50 grid).

Terrain is made up of several layers and the engine optimizes these. Rather than have one single terran layer, I used multiple in order to produce "seams" between layer types, e.g., the geometric boundary between rock and grass in this picture:





Blockgrids

Next are blockgrids, used for houses, walls, castles, and certain features (e.g., the outside portion of wells).

Blockgrids are basically made up of textured blocks; they are sharp-edged and textured, vs. the smooth-edged and non-textured terrain-- a nice contrast.

Notably, the blocks are only half as tall as they are wide, which allows for stairs and other interesting effects, such as the top row of white blocks here:





Objects

After that comes objects. These are generally "static" things, such as rocks, trees, grass, and the like.

Each object has many, many properties such as shadow darkness, a flag and footprint for if they are solid (e.g., trees have a 1x1 footprint, are 8 blocks tall, and are solid), as well as methods to handle clicks and other interactions.

This makes it generally easy to define new types of objects, which is very important-- Texas has perhaps around 500 different types of objects (and counting!)





Next Time: Drones, NPCs

Stay tuned, because the next three parts are already written! Next I'll talk a bit about enemies and NPCs and how they get put into Texas.

Okay! I got up to three stars, took quite some time. Here is what I liked:

- Laid back feel.
- Controls were intuitive, I like the platforming block mechanic for doing everything.
- Generally it was clear what to do, and fun.
- Graphics and sound are excellent, feels really well produced.

What I didn't like:

- I didn't use more than 2 boxes, and 2 plots of land; and that, only barely. The upgrades felt a bit too expensive, or something.
- I wanted seeds to jump right to my boxes.
- I didn't understand the main benefit of boxes was to store food so you could always be working.
- I upgraded my fishing rod once.
- The game definitely felt grindy towards the end.
- I was afraid to hit the "?" box and/or I thought it would only do anything after I beat the game.

That's it! I think the game is completely intuitive on the surface level, but the economics of it feel a bit steep and unrewarding. It would be cool for instance to see your sushi bar expand, and/or take in more money as it gains stars (which only makes sense).

The other thing is I kept worrying that like, if I walked off the dock or into a pit the game would end. After I beat the game I tried and found there were invisible walls. Part of my kept thinking there would be some weird double meaning and like, there was some underwater platform shooter all along and I just had to jump off the dock.

Great job!

neoshaman, put a litle more effort in your English, please. It's difficult to read your posts sometimes.

i tried my best :/
I will seek more supervision then

Neoshaman: I really don't have trouble understanding you, I think you're English is fine and I often appreciate your point of view. Please keep contributing!

Melly: Harsh.

Edit: For your own edification and amusement, please note my improper use of "you're". English is my first language. =) So there you have it!

In Body Harvest for the N64, one of the vehicles you can drive is a combine. You can use it to run over zombies, which gives you shotgun ammo.

Body Harvest is awkward and in many ways broken, but incredibly ambitious and really fun to play if you can get into it.

I have no idea what is going on in this thread. Can someone enlighten me?

EDIT: Okay, we *ARE* talking about Super Columbine Massacre RPG. Nevermind then!

We'll make sure that next time Chevy comes to Edmonton, you can make it to, Psysal. 

(As neither myself nor Matt are making the trip to Winnipeg either).

That sounds awesome! It was great to meet you guys at ggj, I've often thought about heading up to Edmonton if you did another jam...

Ah, this was a really hard decision but I think I am not going to be able to make it. Really it's just that my partner and me took a trip to Seattle for two weeks already in May, she is starting a new job, I'd have to ask time off work (the Monday), and I'm trying to get back into the groove of life. Hopefully that doesn't sound too silly, but somehow the idea of travelling again is kinda stressing me out!

Well, anyhow that's probably TMI. You guys are organizing and awesome event and I wish everybody the best! I'm there with you in spirit...

.... Aaannd because you liked that one, here is a Megaman 2 remix, of Wood Man's stage:

http://kittylambda.com/files/PsySal_-_Megaman_2_Wood_Man_Funkygetten_X-tal_Remix.ogg

I remember hating this so badly when I finished it, I think because the detail perhaps warped my brain. But listening to it now for the first time in like 10 years or something, it's really good! =)

http://kittylambda.com/files/PsySal_-_Faxanadu_Taco_Salad_Mix.ogg

I didn't really create this today, but I encoded it as ogg and uploaded it to my site. It's a remix of Faxanadu music, and a bunch of other game music. I made it a looong time ago, but am still really proud of it. I think I made it about 10 years ago...

Erm. "10 years ago I created..."

This is absolutely amazing. Have a list of the songs?

I made this so long ago that unfortunately I can't remember. I think there was only one tune from faxanada, another from FF2e and the overworld from DQ1. But I am pretty sure there are others buried in there... =) Glad you like it!

http://kittylambda.com/files/PsySal_-_Faxanadu_Taco_Salad_Mix.ogg

I didn't really create this today, but I encoded it as ogg and uploaded it to my site. It's a remix of Faxanadu music, and a bunch of other game music. I made it a looong time ago, but am still really proud of it. I think I made it about 10 years ago...

Erm. "10 years ago I created..."

Hey guys, I am finding this pretty irresistable. So much so that I can't even spell irresisteble.

Two questions, apologies if these were in the thread and I missed it:

- Can I register now even if I will maybe not be able to make it? Or will that really mess things up for you guys?
- What are the accomodation options? I also can't spell accomedation. Like is there a nearby hostel or maybe we can just sleep on the floor at the studio or...? Maybe just not sleep at all, like Chevy! Lately I'm not far from it, actually...
- What's the best times to plan for? Like if I have to leave at 7pm on Sunday night will I miss stuff? Like is there going to be a pillow fight on Sunday night starting at 7:15, followed by a meeting with the past governor general Adrienne Clarkson and her good friend David Suzuki who will award us medals? I wouldn't want to miss this and I know it happened last year...

My options are like, fly in Friday AM, bum around Winnipeg or hang out with some cool game developer dudes (dudettes?) then fly out Sunday PM (or Monday AM) which is going to cost about $500.

... or Greyhound it in on Friday AM to PM, and back Monday AM to PM. This looks to be about $300.

I don't really mind the Greyhound though I have a weird feeling my wife will rather if I take the plane.

I like it too...

The run button broke a lot of the level design, that's all.

Woot, congrats Matt this game is awesome. You also got mention on IndieGames.com and GameSetWatch... =) The strangest thing is that they always credit you as the creator of Broken Cave Robot, i.e., it's not Matt Thorson (Jumper) or Matt Thorson (An Untitled Story) it's Matt Thorson (Broken Cave Robot). Hmm...! Well NEVERMIND it's an awesome game and that is really all that matters.

i've been wondering what's happened to bdtuw.

Yeah me too.

This looks cool but kind of mystifies me that it wouldn't *use* SDL in the first place, hemmm... At any rate I was going to look at this but if it's not for linux that's kind of a deal killer for me. Still, this looks cool.