Author Topic: [Programming] Organizing Data  (Read 5724 times)

Offline Draco18s

  • Resident Velociraptor
  • Core Member Mark V
  • *****
  • Posts: 4,251
[Programming] Organizing Data
« on: July 17, 2013, 11:06:38 am »
I've come to the conclusion that the way I've arranged the information and objects for a game project I'm working on is far from ideal.

I've realized this primarily from having to rewrite the entire game from the ground up, it was originally AS2 and built in very poor way.  I'm redoing it in AS3.

Basic premise:
 - There exists a collection of game levels, each level has a "puzzle" that when solved rewards the player with an item.  Solving the puzzle (or really any puzzle) is required to complete the game, it does however, make it easier.
 - There exists a collection of rewards, most are beneficial, some are detrimental.  Some are beneficial or detrimental based on another collected item.*
 - The game is partially random, partially fixed.  Random elements are determined once (until a user deletes their save files, the in-game reset won't rerandomize the random factors).  This insures that the player can learn the game and eventually complete it entirely.

How the randomness should work:
 - Game randomizes the level order
 - Game randomizes the reward order
 - There are fixed points in the system (e.g. level 1 is always first, the first boss is always level 10, the Dragonscale Sheild is always awarded on the level with the dragon, etc)
 - Game saves this info forever

This insures that strategy guides will have to be vague, as each player will have to figure out the game for themselves.

Problem is, how do I arrange this data internally in a format that is easy to use, easy to save, and easy to randomize?

My original solution was to have, effectively, 3 arrays:
 - The floors themselves (this was a movie clip with frames, so to get floor 5, I could tell this movie clip to "goto and stop on frame 5")
 - The order of the levels (so levelOrder[5] stored the actual floor number)
 - The order of the rewards (so the reward for level 5 was itemOrder[5])

The problem comes when I need to shuffle things, if floor 5 is the dragon that rewards item #5, then any time I move '5' around in levelOrder I also need to move it to the same index in itemOrder.  But I can't move floor 1, 10, or 25 (and some others).  As well as some items needing to appear earlier than others.

Roughly speaking, Flash save files are comparable to NBT data: I can save strings, integers, etc. and arrays of simple data types.  But I can't save custom classes wholesale, I have to hand-write a save/load line for every property.

So ignoring the hassle of trying to figure out why on earth I had Item#26 at a fixed point in the array (not to mention checking it twice in a row), is there a better way of going about this?

*The potion of experience (go up a level) and the potion of forgetfulness (go down a level) are the same reward, but you only get the former if you are carrying an Amulet of Balance (reward from a previous level, and there's six of them in the game, one for each reward with this behavior).

Offline x4000

  • Chris McElligott Park, Arcen Founder and Lead Dev
  • Arcen Staff
  • Zenith Council Member Mark III
  • *****
  • Posts: 31,651
Re: [Programming] Organizing Data
« Reply #1 on: July 17, 2013, 11:19:36 am »
Generally speaking, what we do is manage things as objects -- custom classes -- in our own code, for the sake of clarity and readability.   Arrange this in proper OOP fashion so that it is easy to maintain and work with in code.  Ignore saving considerations for that.

Now have a "serialization" function on each object that you need to save.  This basically looks at the relevant fields that it wants to save from that object (only the fields that are persistent; there may be 300% more working variables that do not need to be saved).  And then it saves those variables as simple types, no problem.  Then there needs to be a deserialization method, and it just creates the object and sets the fields from that.

There are two basic approaches to serialization, each with pros and cons:

String serialization:
Convert everything into big strings, with field names and then a delimiter and then the value, and then newlines (or whatever) to separate fields.  And something else to separate objects, etc.  There are a variety of ways to organize this in terms of how it flows in and out through serialization.  This approach is flexible and easy to manage old and new versions.  When you are parsing this data in deserialization, you just look at the field name flags and do whatever you want.  If you want to stop saving a field in a future version, you just have it ignore those field tags.  If you want to have it load an old version that is missing some field tags, that will work just fine and use default values, no problem.

We use this approach for our settings files in our games.  They are small and don't need to be efficient.  But they do need to be hand-editable, which is another benefit of this approach.  You can just crack open a settings file and make changes, which is really nice.

Binary serialization:
There are varying degrees of complexity you can do here.  But basically the gist is that order of operations is IMPERATIVE.  You know that you start with X operation (like saving out or loading in the levels).  The first item is perhaps a count of the number of levels.  It then calls the deserialize-level method X number of times, where X is that first integer you read in.  Then it does the same thing for your other data types, etc.

This is more brittle, but smaller and quite powerful in general.  You can also make it backward-compatible by including an "overall serialization version" as actually the first thing you serialize and deserialize.  And then every time you make a serialization schema change, you increase that serialization version.  That way you can have deserialization branches and conditionals based on the serialization version that it reads in, which retains your flexibility.

This type of serialization requires a lot of diligence, but it's what we use on all our main data for the Valley games, Skyward, and Bionic.  We might use it for AI War now, I can't recall.

Bottom line
In-engine object organization and the serialization/deserialization of those objects are two separate considerations.  Treat them as such, and you'll get the best of both worlds when you do each specific sort of action.

And I can sympathize on being frustrated with your earlier designs.  It takes a while to find something you love.  In 2002 I did one game, then got to a point where it was just interminable, and I trashed the engine and started over in 2003.  Then that became the basis of Alden Ridge, but then I trashed that three times in 2008 and made major overhauls.  Then that became the basis of AI War, which then evolved a number of times and trashed a lot of older concepts.  Then Tidalis did a lot of the same, and those ideas got retrofitted into AI War.  Then the same with Valley 1, and those also got retrofitted into AI War (not Tidalis though).  And so on.

Engine work is always a work in progress, I think, heh.
Have ideas or bug reports for one of our games?  Mantis for Suggestions and Bug Reports. Thanks for helping to make our games better!

Offline Draco18s

  • Resident Velociraptor
  • Core Member Mark V
  • *****
  • Posts: 4,251
Re: [Programming] Organizing Data
« Reply #2 on: July 17, 2013, 11:28:32 am »
Alright, that's understandable.

But any suggestions on how I'd arrange the data?  That is, how many different objects should I split things into and what would each one know?

That's really where I'm getting stumped.  Serialization is more of a hassle than anything, took me most of yesterday just to save/load the player object properly...which is also something like 90% of the data currently being saved (the rest of it is this, and comprises only a handful of arrays).

Offline x4000

  • Chris McElligott Park, Arcen Founder and Lead Dev
  • Arcen Staff
  • Zenith Council Member Mark III
  • *****
  • Posts: 31,651
Re: [Programming] Organizing Data
« Reply #3 on: July 17, 2013, 11:49:00 am »
Well, object arrangement is somewhat down to personal tastes of the programmer -- and by that I mean, their style of thinking.  Different people think of hierarchies in different ways, and are comfortable or uncomfortable with looking at code in different arrangements.  I run into that a lot when looking at other people's code, even if it's well organized but just feels foreign (in terms of thinking styles).

That said, if it were me, I'd arrange the data you note as follows:

- A central singleton class (let's call it Game) that manages the data for everything else.  The root serialization method would also be here.

- A list of LevelDatas on Game; one instance of LevelData per level.
--The list would be randomized as desired, right in that list on Game.  Easy peasy there.
---Specifically, do perfect randomization first.  Make it super super random, and forget about your rules with level 1 and 10 and such.
---Once the whole thing is random, do a second pass: find level 1, and switch its position with whatever is in the first slot.  Then the same for level 10, etc.
--The puzzle data would be on LevelData, as would whatever metadata about player completion statuses, etc.
--When you start a new game, all that data about level order is just as relevant as player completion statuses, so it makes sense to have all that here in one place.

-A list of RewardDatas on Game; one instance of RewardData per reward.
--The list would be randomized as desired, right in that list on Game.  Easy peasy there.
---Again start with perfect randomization, then find the rewards that must be in certain slots and put them there.
---If there are other specific ones that must be in certain slots that match the random position of a level, then first find the slot of that other reward, and then do the same position swap again here.
--The "has the player gotten this reward" would be stored on here.
--When granting a reward, it looks for the first reward in the list that hasn't been granted, and gives that.


This isn't really that different from what you were doing; the main difference is the two-stage randomization.  If you preferred having the rewards specifically be on exact levels, then you could do that.  If you wanted different groups of rewards prior to level 10 and after level 10, you could do that too -- just put them into working lists, shuffle them up, and then insert them into the main list.  So if 1 and 10 are fixed, then you take items 2-9 into a working list, shuffle them, and then put them back.

Am I missing anything in your requirements?  I think I hit all of it...
Have ideas or bug reports for one of our games?  Mantis for Suggestions and Bug Reports. Thanks for helping to make our games better!

Offline Draco18s

  • Resident Velociraptor
  • Core Member Mark V
  • *****
  • Posts: 4,251
Re: [Programming] Organizing Data
« Reply #4 on: July 17, 2013, 12:57:47 pm »
*Sound of whirring gears*

I've pretty much got a LevelData object already, though right now all that class does is handle converting the visual level into array data for pathing/collisions, but that class would be extended in order to handle the puzzles (just haven't done it yet, foundations first then game specific logic).

Handling RewardData, I hadn't thought of doing the same way, originally it wasn't needed, the items themselves were just buttons in the inventory (arranged on start to the correct order) and handled their own activations via Bad-Form-AS2-Code-On-Objects.  The rest of the code only needed to know a single integer about it.

I think the easiest way to handle the randomization going this way would be to use a seed-based random (rather than calls to the native random function) and saving only the seed (randomized on first run, per normal), rather than trying to serialize an array of complex objects.  Instead just store the relevant information for those objects (acquired, solved, etc.) and essentially "reshuffle" on every run and the saved/fixed seed would insure identical order.

Offline x4000

  • Chris McElligott Park, Arcen Founder and Lead Dev
  • Arcen Staff
  • Zenith Council Member Mark III
  • *****
  • Posts: 31,651
Re: [Programming] Organizing Data
« Reply #5 on: July 17, 2013, 01:02:48 pm »
Yeah, we do a lot of that sort of thing for secondary bits of data, too.  Not always, because that approach causes big issues as soon as you change the algorithm at all (so if you plan on updating the game later -- even adding one single new level -- it will not unpack the same way at all).  But you could use something like this: http://www.cs.gmu.edu/~sean/research/mersenne/MersenneTwister.java

It's fast and much more accurate, and can be adapted into whatever languages.  In our case C#.
Have ideas or bug reports for one of our games?  Mantis for Suggestions and Bug Reports. Thanks for helping to make our games better!

Offline Draco18s

  • Resident Velociraptor
  • Core Member Mark V
  • *****
  • Posts: 4,251
Re: [Programming] Organizing Data
« Reply #6 on: July 17, 2013, 01:16:31 pm »
Yeah, we do a lot of that sort of thing for secondary bits of data, too.  Not always, because that approach causes big issues as soon as you change the algorithm at all (so if you plan on updating the game later -- even adding one single new level -- it will not unpack the same way at all).

Not an issue here.  The game design doesn't really support additional levels post-release.  In theory it could but I'm not going to worry about it.  50 levels, flat.  Well, technically 53 but even that's a spoiler.  Think more classic Angband ("reach the bottom, kill the boss") than TOME or ADOM ("all kinds of places to go!").

Quote
But you could use something like this: http://www.cs.gmu.edu/~sean/research/mersenne/MersenneTwister.java

It's fast and much more accurate, and can be adapted into whatever languages.  In our case C#.

Yup, I know of it.  I do play Dwarf Fortress afterall. ;)
There are other randomizers, of course.  There was one that was really simple, forget the name off the top of my head.  Wasn't as objectively random as Mersenne, but was "good enough" for applications like mine.  Trying to remember where I saw it and what I ended up using it for...

Offline x4000

  • Chris McElligott Park, Arcen Founder and Lead Dev
  • Arcen Staff
  • Zenith Council Member Mark III
  • *****
  • Posts: 31,651
Re: [Programming] Organizing Data
« Reply #7 on: July 17, 2013, 01:20:30 pm »
Got it, makes sense.  And in terms of added levels, I mainly meant if you decided to go back and add more later.  You never know, if it's popular: even things like Rebuild got added to quite a bit.
Have ideas or bug reports for one of our games?  Mantis for Suggestions and Bug Reports. Thanks for helping to make our games better!

Offline Draco18s

  • Resident Velociraptor
  • Core Member Mark V
  • *****
  • Posts: 4,251
Re: [Programming] Organizing Data
« Reply #8 on: July 17, 2013, 01:25:54 pm »
Got it, makes sense.  And in terms of added levels, I mainly meant if you decided to go back and add more later.  You never know, if it's popular: even things like Rebuild got added to quite a bit.

Like I said, not worried about it.

If it comes to it, I'd just rerelease as a new game.

Offline x4000

  • Chris McElligott Park, Arcen Founder and Lead Dev
  • Arcen Staff
  • Zenith Council Member Mark III
  • *****
  • Posts: 31,651
Re: [Programming] Organizing Data
« Reply #9 on: July 17, 2013, 01:55:44 pm »
Makes sense.
Have ideas or bug reports for one of our games?  Mantis for Suggestions and Bug Reports. Thanks for helping to make our games better!

Offline Draco18s

  • Resident Velociraptor
  • Core Member Mark V
  • *****
  • Posts: 4,251
Re: [Programming] Organizing Data
« Reply #10 on: July 17, 2013, 04:42:19 pm »
Thanks X.  This is working out quite well.  Going to have fun linking up some of the interactions, but nothing super crazy* (I would have had that trouble anyway, just in a different form!).

*was item on floor y picked up, when does item x activate (and how do I attach that event listener), etc.

Offline x4000

  • Chris McElligott Park, Arcen Founder and Lead Dev
  • Arcen Staff
  • Zenith Council Member Mark III
  • *****
  • Posts: 31,651
Re: [Programming] Organizing Data
« Reply #11 on: July 17, 2013, 04:51:40 pm »
Awesome stuff!  Glad I could help.

And a couple of notes, apologies if these are a bit basic; but these are things that even I will sometimes slip and forget when I'm distracted with a tougher problem:

1. Make sure that you have one central method for determining those "not super crazy" things.  So long as you only have to code and test it once, and then just call it in that one way from then on, the complexity of that one thing doesn't matter too much.  Even if that's called from all over the codebase.

2. Event listeners...?  Yeah... Keith likes doing those, too; well, delegates that then get triggered in various ways, anyhow.  I used to write event-driven code as well, and I have picked up his habit of limited-use of delegates.  But generally speaking I find it really makes code incredibly harder to understand if there are a bunch of events being triggered all over the place.  For one thing, the order of operations tends to matter, and the order of which event gets triggered first if something triggers multiple events or an event with multiple listeners can get... dicey.  Plus you have the complexities of registering and deregistering listeners.  I really prefer to be able to just look at the state and then make the appropriate method calls at that time; that way the evaluation code and the execution code are clearly linked, both in terms of the codebase and the call stack.

It requires a bit of a shift in mentality, but I would advise against excessive event-driven stuff in games.  Most games programming tends to be main-loop oriented, callbacks and other asynchronous stuff aside.  Obviously there are a lot of benefits to event-driven coding in certain circumstances, but I've even moved away from doing that for keyboard/mouse/etc input (I initially moved that way because DirectX moved that way).  Instead of having events, having basically a device-polling model that gets looped across can be a lot more controlled because you can control the order of everything.

Those are just my personal prejudices of course, and not everyone agrees.  But you asked about code architecture, and when someone says "event listeners" and "I'd like to keep complexity down" in the same sentence, it sets off my spidey sense. ;)
Have ideas or bug reports for one of our games?  Mantis for Suggestions and Bug Reports. Thanks for helping to make our games better!

Offline Draco18s

  • Resident Velociraptor
  • Core Member Mark V
  • *****
  • Posts: 4,251
Re: [Programming] Organizing Data
« Reply #12 on: July 17, 2013, 05:22:31 pm »
And a couple of notes, apologies if these are a bit basic; but these are things that even I will sometimes slip and forget when I'm distracted with a tougher problem:

I know how that goes.

Quote
1. Make sure that you have one central method for determining those "not super crazy" things.  So long as you only have to code and test it once, and then just call it in that one way from then on, the complexity of that one thing doesn't matter too much.  Even if that's called from all over the codebase.

Yup, already do.  In my floor class(es) I've got a function for goUp, goDown, getKey, and getTreasure.  The item classes have an applyImediately function that always gets called as soon as the item is acquired, and another public function which will be the "this item has been activated from the inventory" mouse-click handler.

Quote
2. Event listeners...?  Yeah... Keith likes doing those, too; well, delegates that then get triggered in various ways, anyhow.  I used to write event-driven code as well, and I have picked up his habit of limited-use of delegates.  But generally speaking I find it really makes code incredibly harder to understand if there are a bunch of events being triggered all over the place.

Trust me, I know that horror.  I once had to finish a project that used that model to the extreme.  One class fired off an event which was picked up by another class, which all it did was fire off a different event.  It took me the better part of an hour tracing those events up the stack.  This isn't going to be that nuts.  The events I'm talking about are more conventional events that have very specific actions:

Mouse clicks
Mouse over/off (for tool tips)
On Update Tick

I've got two (so far) custom events in order to handle a few edge cases, mostly because the bottom-most class isn't aware of the main game class or the stage/scene.  So when a creature takes damage, the Attributes class fires off a TOOK_DAMAGE event, which the main game class picks up (through references it can get access to) in order to attach a floating number to the visible screen.

Quote
Those are just my personal prejudices of course, and not everyone agrees.  But you asked about code architecture, and when someone says "event listeners" and "I'd like to keep complexity down" in the same sentence, it sets off my spidey sense. ;)

No worries.  I don't use event driven code, I try to stay away from it, but buttons kinda have to with AS3.  There's no really good way around it (the alternative is a game loop that polls the mouse, then hit tests the mouse location against every (mouse-capable) object in the scene, which is not exactly the fastest thing in the world with Flash).

And then there's the occasional "this object doesn't have a reference to that object, and by rights shouldn't, but it needs to make something happen there" that is easily solved via custom event.

Offline x4000

  • Chris McElligott Park, Arcen Founder and Lead Dev
  • Arcen Staff
  • Zenith Council Member Mark III
  • *****
  • Posts: 31,651
Re: [Programming] Organizing Data
« Reply #13 on: July 17, 2013, 08:17:45 pm »
All makes sense!  When there are event handlers that do all that sort of heavy lifting for you, good god I would not reinvent that wheel.  I thought it sounded like you might be doing more inter-object messaging via events, but from what you say it sounds great.
Have ideas or bug reports for one of our games?  Mantis for Suggestions and Bug Reports. Thanks for helping to make our games better!

Offline Draco18s

  • Resident Velociraptor
  • Core Member Mark V
  • *****
  • Posts: 4,251
Re: [Programming] Organizing Data
« Reply #14 on: July 17, 2013, 08:43:07 pm »
All makes sense!  When there are event handlers that do all that sort of heavy lifting for you, good god I would not reinvent that wheel.  I thought it sounded like you might be doing more inter-object messaging via events, but from what you say it sounds great.

Nope, I don't do all interobject communication with events, that's a mess!