Show Posts

This section allows you to view all posts made by this member. Note that you can only see posts made in areas you currently have access to.


Messages - Skullcoder

Pages: 1 [2]
16
Programming / Re: Heterogeneous saving and loading objects in C++
« on: April 05, 2016, 06:31:20 PM »
Java also uses a similar method under the hood for its serialization protocol, whereby the type is written before the data; But type alone is not the only consideration to make if you're talking about generic object storage and instantiation...

I've done something similar back in C99.  When porting my OOP system to C++, and before the introduction of run-time type inspection to C++, I had included a type ENUM and a macro which when inserted into each new type would add a new entry to the OB_TYPE_ID enumeration, and assign that as the static ID of the type.

At the time I had created a scripting language with tight bindings to C which allowed C code to transparently read/write properties and call functions on script objects using some preprocessor and macro magic (rather than eval("script code") or similar as seen in Lua and other embedded scripting langs).  In constructing my Object class (building custom OOP within C), I included the run-time type ID by default, and a registration system which allowed objects to register the default instance of themselves with a factory.  Then factory->OB_Instantiate( dataptr ) would read a type ID from the dataptr, advance the pointer, look up the object registered for the ID, then call the (script provided) function Object->clone()->load( dataptr );  In addition to polymorphism this allows "prototypical" behavior since scripts could replace objects with new objects that provide more / new functionality via registering a compatible subclasses for a TypeID -- However, that form of dynamism is purely optional.  Of course the gnarly script-required calling semantics in the host language were hidden behind a macro...

When registering a type with the factory, one also registered its property definition, of interest was the offset of pointers within the object data which could reference other objects that also needed to be saved or loaded.   In the OB_Instantiate() function the property definition for the clonee would be queried to determine if there were any references to other objects that the object needed to load.  It would then "recursively" (via iterative trampoline) load all of the objects referenced by this object.  This allowed me to perform loading and saving of the entire game state via a single save( game ) or load( game );

One issue I ran into (but you may not, since my implementation was meant to serialize general purpose language objects rather than a specific set of pre-known classes), was that that several objects could reference the same other object.  This means that I not only needed to record the type of the object ahead of its data, but also the globally unique identifier of the object instance; Otherwise, when saving or loading data a single object may get turned into multiple separate instances (due to its reference by other objects).  Since repeated saving was benchmarked as more frequent than loading events I optimized for save speed and the unique ID was implemented simply by storing the integer value of the object's pointer prior to its type ID and property data in the stream.  I also marked each object as "saved" in the memory management bookeeeping header that precedes all object instances... more about this later.  If you're not using a custom allocator and can't rely on bookeeping metadata for the object instances then you can incorporate the "saved" flag into the lower or upper bit of the type ID, or use a map as a key / value store to keep track of which object pointers have been saved.

When storing an object I first determine whether or not it's already been stored by querying its status bit (or you can query the "saved" map for the existence of its pointer (key)).  If the object is already saved this "batch" then I don't need to write the Type ID nor any instance data, only store the pointer to the object data in the output stream (or an otherwise unique per object instance number).  If the object pointer to be stored is NULL then only the NULL pointer value is written and the storage function does not recurse.

When loading the data the pointer values loaded do not reflect the actual memory location of an object, of course.  However, they are unique and thus allow me to build a key / value store when loading (I use a hashmap, but a treemap or other map will do).  To perform loading I first read the object's unique instance ID (its old pointer) from the data stream, then I test for the existence of the key in this batch's "loaded" map. If the key does not exist then the object is instantiated using the type ID and data from the stream; The new object instance pointer is added to the the map as the value for the key of its "unique ID" (the old pointer loaded from the stream).  The new instance pointer is returned from the instantiation factory function (which might be returned directly, or be setting the property of another object being loaded).  If the key does exist, then its value (an instance pointer created this loading batch) is returned instead of instantiating a new object from the data stream.  The special case of NULL is addressed by adding "NULL:NULL" (0:0) to the key:value map prior to loading a the batch of objects.  Thus if an object has a pointer property that may reference another object type, but is set to NULL, then a new object of that referenced type is not instantiated, the pointer gets set to null as intended.

A note on bit-flag optimization: I was able to avoid plaicing a "saved" flag in the TypeID or using a map structure during saving since I had a custom allocator and garbage collector which provided some metadata prior to the object's pointer.   In C and C++ when you call malloc() or new() the pointer value returned is typically advanced just beyond some record keeping data that is needed for the allocator to locate the memory management structures in order to free() the data.  The free() or delete() function typically subtracts some constant value from the pointer passed in and this gets you to the memory management record keeping header data which then allows the standard lib (or kernel) to return the memory to the process's (or system's) memory pool.  Since all of my allocation sizes are limited to aligning on word boundaries of the platform (16 or 32 or 64 bit = 2, 4 or 8 bytes), and I recorded the size of the allocation for range checking and to determine which size-range specific allocator to use: I was able to use the lowest bit of the "size" field of the allocation's GC header data as the "saved" bit, the low bit was simply masked off during free().  So, if you request 7 bytes you'll get allocated 8 usable bytes (round up to the nearest word boundary) + some header data (a "size" word, in this case), and the pointer returned will point to the usable data just beyond the memory management header.   That's simply the overhead of dynamic memory allocation.  Knowing this, however, allows you to place global record keeping information (such as a "stored" or "loaded" flag, or even the runtime type IDs) outside of the "user's" object definitions.  This is how C++ provides your run time type data for introspection (on supporting compilers), beware that it may not be standardized across compilers, thus making it somewhat useless and necessitating a "roll your own anyway" approach (which I find, unfortunately, quite a common occurrence in C++).

You can provide your own compiler agnostic global instance data by overloading malloc() or new() and requesting a few bytes more from the underlying functions in order to store your record keeping data.  Before you return the pointer, just be sure to advance the value returned from the underlying functions beyond your record keeping header.  You'll also have to overload free() or delete() and manually modify (and reinterpret cast) the pointer value so that it actually points to the top of your object+header.  Users of the returned value thus remain unawares that there's extra stuff before the instance pointer.  Using this, and potentially a macro or two in your object definition, you can keep the clutter to a minimum rather than requiring each Object class to have unique code that explicitly performs serialization of its data.  Note that if you decide to extend all objects from a root GameObject class, that including the typeID field in the root object may quickly slam your head into the object inheritance diamond problem.  This is due to an absurd deficiency in C++ whereby the "virtual" keyword is applicable to methods, but not instance variables...  If only variables could be declared "virtual" (and thus their position data added to the same VTABLE that "virtual" functions are), then C++ would be far less retarding to the implementation of advanced functionality as "pure virtual" classes could then contain vars (and templates wouldn't have to take up so much of the slack).

Of course this is only one way to achieve the goal of generic global object save / load functionality.  Each will have pros and cons.  I primarily posted this to bring up the issue of deduplication & instance resolution.  Look into the custom Allocator facilities that C++ provides, and esp: Per-class overriding of the new operator.

A word on the type property definition: For the purpose of object serialization one only needs to record the number of object pointers within the type data record, and the offset of each pointer within the type record.  This can be trivially constructed by using a macro to create your type definition and a macro to declare pointers to objects within said type definition macro (or crazily constructed using a set of C++ template functions which abuse the preprocessor to perform addition and address-of operations to construct a "class_def" symbiote to make up for the lack of proper introspection, and once again "roll your own anyway").

17
Design / Re: map with complex numbers
« on: April 01, 2016, 04:05:03 PM »
Perhaps not in the domain of "complex" numbers, but one method of visualizing various attributes is through layering of multiple dimensions.

For example, a scent, heat, or luck dimension can be extracted from and/or applied to the entities within a given spacial region.

Additionally, an entity may exist within a complex dimension whereby its X,Y,Z coordinates are only the visible representation and, as Xecutor mentions, additional dimensions of spirit, health, skill, elemental affinities, etc. are frequently present though rarely visualized as contiguous dimensions.

For example: the player's favor may exist as a point in the complex plane of a god's will, which is a field encompassing the combination of dimensions said god presides over, such as luck, vitality, vengence (critical strikeness), etc.  Some sort of collapsed visualization of the complex plane may assist in informing the player of their current status even if it may be unclear to them how their actions multiply, translate and rotate them through the god's complex plane of consciousness.  Perhaps a chaotic god could modulate their perceptual domain via the Julia set to demonstrate a deterministic graph of their fickle nature.

Derivations of the players path within the complex plain of possible player statuses could be useful for automatic leveling of related stats.  As for physically navigating in N+ dimensional space (keeping in mind that time is the unstated 0th dimension where "2D" and "3D" games are concerned)...  I have not yet demonstrated a sufficiently navigable display in my experiments, but I believe one approachable method may be rendering outward from the local dimensional origin rather than rendering the player's position from the global perspective.  Rendering deviations from the local origin would have the tendency to show the immediate surroundings in the complex plane as more normal, and potentially more warped and strange the further objects are from the player's point of view.  I've yet to implement this, however.

18
Design / Re: Conway's Spikes
« on: April 01, 2016, 03:30:04 PM »
[...] I have the floor change color a few turns before the spikes pop as a warning to the player.

That's a nifty feature.  Do the enemies know about the spike pattern, or are they alerted the same way the player is, or perhaps there's only flying foes on the floor?  I suppose, if especially devious, the spikes are the only foe required for that floor.

Do link us to any publicly displayable progress when possible.  I'm interested to see how it works out.

19
If one were crazy enough to implement a new programming language expressly for roguelikes, and possibly even a (virtual) chipset expressly for running said language upon, and potentially even a portable cross platform (virtual) operating system atop said chipset expressly to support the integrated development of roguelikes, what features and/or syntactical sugars might one expect to find therein?

Let's assume that the language's standard library would have the expected bog standard algorithms for pathfinding and procgen, such as A*, voroni, perlin & simplex noise, etc. as well as abstractions for recording and retrieving the game state and levels via the platform's available storage medium.  Let's also assume the standard library includes a tile based display interface capable of multiple layers of ASCII or graphical and potentially animated cells / sprites, something a bit more friendly than curses but in a similar vein, with definable "window" objects and scrolling regions within the display, etc.  And while we're at it let's assume there's a simple music and audio event system included.

I'm not asking what standard tools a roguelike programming language would want to have in a standard language library as that's quite apparent from existing frameworks, but rather I'm curious to discover what, if any, linguistic flavoring could prove more "expressive" for roguelike development than existing general purpose languages?  For example, in my experience roguelikes tend to be extremely stateful.  So, perhaps a roguelike language would have builtin Actor entities an in addition to the generic OOP features these would have "states" and "statuses" which can affect the actions the Actors perform.

Thus:
Code: [Select]
Actor enemy = new rand Enemy of [ floor.actors with[ Enemy ], currentDifficulty, floor.environmentType ];
...
enemy: if ( has Pain ) is Angry;
// Equivalent to:
// if ( enemy has Pain ) enemy is Angry;
...
enemy: if ( can See( target ) ) attack();
// Equivalent to:
// if ( enemy can See( enemy.target ) ) enemy.attack();

The above would create a new Actor of the Enemy type, randomly selected from those registered types matching the current set of "of" qualifiers: Actors of Enemy type available on the current floor, at the current difficulty setting and matching the current floor's environment status.  The union of qualifiers represents the pool from which the enemy's type would be randomly selected prior to instantiation.  The pseudorandom "rand" selector being deterministically seedable at the outset, of course.

Then the enemy.attack() function may perform a different set of logic depending on whether it entered the "Angry" state due to it having the Pain status, i.e., more than one set of "methods" could be registered for the Actor, and if the Enemy has an Angry state that defined a different .attack() method, it would be called rather than the Enemy's default attack() method.

The attack() function(s) would not be called if the status of sighting its current target is missing.  Furthermore, the state transitions would have a default "on" method that is called when entering such a state:
Code: [Select]
Dragon:Enemy{
  ... 
  on: Pain{ is Bleeding; }
  on: Death{ floor.addAt( self.position, new rand Drop of self:[ drops, inventory, floor.level ] );
  ...
}

Also note the "with [object]" shorthand of "[object]:", which selects the given Object/Actor/Entity as the default scope for the duration of the following statement / block.

A form of compile time static type analysis could generate warnings if unique / non-eventful, and possibly misspelled statuses/states are applied to Actors.

This is a hypothetical syntax, of course; I'm only mostly crazy enough to implement such a domain specific language, and can neither confirm nor deny whether several iterations of cross platform virtual machines already exist and are hungry for construction of a language other than Assembly or C... Mostly, I'm interested in what features / syntax others would envision an RL lang of having.

The obvious response that few if any would bother tinkering with a new language just to utilize some newfangled portable rogulike operating system is a given; Thus, please ignore the difficulty and insanity required to achieve such a goal and instead approach the question as an outlandish thought experiment:
What if...

20
Design / Re: Conway's Spikes
« on: March 27, 2016, 04:25:25 AM »
If you know anything about Perlin Noise, or Simplex noise, I'd suggest application of something like that.

You could have a selection of noise generators, which are functions that return values between 0 and 1 for a given x,y, and t (time) input.  Pseudo randomly select N noise generators.  Pseudo randomly generate the parameters for them.  Average the result and apply a high-pass filter (say, values greater than 0.75 == has spikes).   A modulo time domain will create the period of a noise pattern's repetition, and the seeds for generation of its parameters (t can be turns, of course).

Modulating with a Voronoi filter or other such filter before the isSpike() calculation can add interesting patterns.  Biasing the result with simple patterns such linear or circular progressive waves towards the exit [ (distance_from_exit * t) MOD period], etc. can add directionality to the movement of the spikes and help prevent impossible spike rooms.

If you are dead set on using Conway's Automata you can simply select N cells pseudo randomly and XOR these same cells every N turns (no need to randomly select a different location each XOR).  This is like re-seeding the automata sim with a known pattern every N turns and will prevent permanent stability perhaps at the cost of the odd long running emergent pattern (as it will be interrupted via the periodic reintroduction of chaos).  You could experiment to discover a good starting "seed" which produces a nice amount of activity, use that seed as a constant for the spike floor, and then only slightly modify it via aforementioned periodic pseudo random XOR so as to have some control over what to expect without absolute pre-determination.  While this may run counter to your stated desire not to simply trigger some traps to mix things up, it is offset by the initial introduction of a known behavior which meets the requirement of being in a somewhat known state.

21
Design / Re: Thoughts on this identification system idea?
« on: August 04, 2015, 11:36:59 PM »
In a medieval-esque fantasy world pre-mass-production there's no real reason to assume that potions made by two different people would be anything alike and prior experience of other healing potions may not help you recognise the kind found in the dungeon.
While that might be true, it begs the question: "Why don't all the potions cause different effects?"  Not that this isn't answerable, it's just that it's equally ridiculous to claim I can identify all health potions as such simply by drinking one.  They could all be completely randomly flavoured, scented, artificially coloured and etc.  If there is a commonality among such items and this dungeon wasn't just created yesterday (or a few milliseconds ago) according to some narrative, then it stands to reason the identification of items in this particular dungeon -- being exceedingly valuable information -- might exist outside the dungeon prior to ones entering it.  For instance, after having discovered the blue pills cause erections I could thereafter describe such pills to others; Indeed, there are many individuals who know what color Viagra pills are, and even though I've never seen one in my life, I know they're typically blue.  That's because information about the pills has escaped the metaphorical dungeon, as would any such information about legendary substances.

Of course, in reality, the dungeon "magically" changes its items identification for each adventurer.

I put it to you that at character creation it's not too terrible an idea to allow some level of familiarity with worldly knowledge to assist one in identification of items.
The potion is blue, like the one your mentor gave after training, but it also looks like the one grandma used to kill weeds.

As for whether this makes things "tedious", it gives a purely optional layer to the identification game.  If one is so inclined they can draw out a logic graph of properties to more quickly identify items.  Or, they can stick to the "classic" identification processes.  I put it to you that players do, in fact, play differently.  Just because an avenue is available doesn't mean one will take it "Every time".  I mean, you can run any Roguelike in a VM and save scum as often as you like... but just because you can drink the potion, die, reload, then know what that potion is, doesn't mean the player will actually take that avenue.

I'm not saying it's the best mechanic, it's just one that is an alternative to the 1st post's "process of elimination" via vastly reducing types available.  It performs the same function (aiding process of elimination) without reducing the types.

Quote
On the topic of realism, though; it has always struck me as very strange that some anonymous wizard goes to the trouble of brewing up all these potions and lugging them into a dangerous underground dungeon to leave them scattered randomly around the place for wandering adventurers to find and yet never bothers to actually label any of them.  That's a pretty weird hobby.
Equally as strange as stuffing gold up monsters' bums.

22
Design / Re: Thoughts on this identification system idea?
« on: August 04, 2015, 10:02:48 AM »
Let's say I'm holding an unknown potion.  In a real pinch, rather than gulp the whole damn thing like a fool I'd probably sip just a tiny bit it and see what the effects were.  Unless it's the most potent of poisons I might still live, or I might only immolate a little bit and survive.  I think I'd find it strange that I'd have lived to at least adolescence (able to carry weapons and shoot bows), and yet no one ever gave me any hints on what common odors or colors some potions might be.  Perhaps I know that health potion smells [sweet | acrid | etc.] just like an immolation potion, but that eliminates a couple of possibilities without revealing the identity completely.

Poor little @, his creators made him a fool so he drinks the whole potion every time without considering any alternative, and he fancies himself an adventurer without ever asking anyone in the (procedurally generated) universe anything about what such a life might be like.  Of course, I might expect this behaviour from a brutish hero, but not from a mage or some such who you would expect would have studied the common color / smell / viscosity / etc. properties and be able to discern the rough probability of a potion's type.  Let's face it: If every potion of "healing" can be identified on sight after the first one is quaffed then there's a good chance there were similar looking healing potions around when growing up, or at least rumours about them.

23
I've used Marching Squares to solve this issue before.  It can still be done in 16 tiles per transition (can look better with a few more for transition, even support diagonals).

The trick is sampling tiles at the corners, or rather that a # for a wall would be sampled at its centre, and thus it contributes to 4 different corners of tiles (tiles are offset 1/2 a tile diagonally from the "grid").  So, it becomes 4 tiles (all corners).  In the data format the method uses two map values per ID (0,1 = 1; 2,3 = 2; etc. basically shift down by 1 bit to get the tile type).  The article explains the sampling method and has a link to a web demo.

So, when you "lower" the terrain value it could create two different types of holes, like how the demo has either diamonds and squares as the smallest road piece depending on the average height of the tiles.  Holes could be like that, but in reverse.  A tiny hole, then a bigger hole.  Make enough tiles and the above could even give you cracks (long holes).

To make the example code work with 16 tiles per transition (no "saddle point" bits) change the last tile mapping to this:

// Samples without extra "saddle" resolution have shape data encoded in the lowest bit.
shape = (sTL & 1) | (sTR & 1) << 1 | (sBL & 1) << 2 | (sBR & 1) << 3; // 4 samples: T = top, B = bottom, L = left, R = right
ring = ( sTL + sTR + sBL + sBR ) >> 2; // Average of samples w/o remainder.
row = ring; // could just use 'row' up there, but included here for clarity in comparison to example code.
col = shape - (ring & 1); // Same as in example.

Pages: 1 [2]