Topics

1

Design / OOP, ECS, Roguelike, and definitions

« on: February 11, 2016, 03:51:49 PM »

These days we're bombarded with one liners, "OOP is bad!", "ECS is the way!", "New Roguelike game!".   Definitions, its all about definitions. 

OOP.. which OOP?  which part of OOP?  which application of OOP?  Like any other part of programming, there are good and bad uses.  I'm not even going to try to enumerate them here, much less address them.  OOP has a place, it fits some things, doesn't fit others.  Misuse of pattern classifications and concepts are a similar, related, even coupled, issue - to me, patterns are for review and refactoring purposes, *not* for up front design.  But hey, good uses, bad uses.

ECS... again which ECS?  The ECS as used in Unity3D?  The ones described here: http://entity-systems.wikidot.com/?  Maybe the one in this paper http://www.dataorienteddesign.com/dodmain/?  None of them are the same.  Some include OOP concepts, some are rabidly anti-OOP.  Which variant fits which problem space?  What are the costs and benefits?  Good uses, bad uses.

Roguelike - fooled you, not even going to touch this one.

Personally, I recall years ago, in another conversation, practically another lifetime, saying "it's all about the data", and when it comes to OOP, ECS, and Roguelikes today, I'm saying "it's all about the data".  As an experiment or proof of concept I'm taking 50+ years of relational database theory and practice and using that - I mean if they haven't gotten it right after all this time, no one has.  No, not sticking SQLiteDB ::memory:: in my game and running SQL against it, but organizing, structuring and accessing my game data in an equivalent manner.  Advantages, disadvantages, we'll see.  No, I'm not calling it ECS, its RDM if you need three letters (Relational Data Model).  And *gasp* it uses OOP in places!!

Anyhow, just had to hop on the bandwagon,
Have a good one,
Brian aka Omnivore

2

Programming / Simple, stable, energy system

« on: January 29, 2016, 11:59:23 AM »

If you are like me and found the need for an energy system to schedule your entity actions, you probably haven't found much clearly stated on the net (or I missed it in my searches).  Implementing an energy system runs into two additional potential problems; multi-move jumps in display state, and possibly an unstable (unsaveable) game state when processing halts due to needing player input.  It sounds like a thorny problem, but after you break it down, it isn't so bad, the following is, I believe, a fairly clean solution.

First, lets deal with the multi-move jumps in display state.  This is where a mob takes two or more actions (typically moves) to the player's one.  If you simply give the display a new state after each player move, you end up with 'teleporting' mobs, jerky actions.  You can, of course, turn to something like a physics engine and do an animated display, interpolating the move over time so it looks good.  However, why not eliminate the problem in the first place?

An energy system works by adding a value based on an entity's speed to the entity's energy state each turn.  In simple systems, an entity with a positive energy level is free to take an action.   The action's energy cost is subtracted from the entity's energy level.

If our display system is typical of today's frame rate driven loops, then instead of doing all the work at once, we can use a divisor to spread the work over multiple frames where each frame (or sequence of n-frames) receives a stable picture of the game state.  The ideal divisor is one that is large enough to ensure that no entity can take two actions in one processing tick.  That is, the fastest speed energy add amount divided by the divisor is smaller than twice the quickest action energy cost.

A nice side effect of using a divisor is that after each processing step we potentially have a stable game state so we can do 'save anytime' save games (useful for debugging at the very least).  Potentially, because there is another wrinkle to the overall problem.  Player entities can normally only act if input from the player is available. 

Part of doing an energy system is ordering actions by entity energy.  This isn't just an afterthought, it is a necessary part of making a consistent acting system.  Typically this is done by sorting or by a priority queue.  Sorting is simpler, and hey, we're doing roguelike, we have cycles to spare (although sorting in this case is probably *faster* than a reprioritizing priority queue).

Now though, we have a dilemma, halfway through our sorted list of entities by positive energy levels (descending), we run into our player entity.  No problem, we say, we'll just grab the next player command out of the input queue and... oops... nothing there.  We're stuck.  We have to bail and return control to the user interface, but we have a half done list, an unstable state.  Sure there are some coroutine hacks that might let us actually yield then resume later, but between the yield and resume we can't save the game state because it is not in a stable state.

There is a simple solution, one that doesn't require saving some sort of quirky interim state.  Before we even start processing the tick, we check to see if A) there is player input in the queue, and if not B) that the player's next energy level won't be above zero.  That is, we check to see if the player's entity is going to run into the stalling scenario above, and simply return from the process game function without doing anything to avoid it.  Maybe that's why my google-fu failed, everyone that has done it considered it too simple to need writing up!

Ok, time for some pseudo code:

GameLoop:
   GetInput => add command to player entity input queue if necessary
   Update => call the engine's Process function
   Render => do what I'm really bad at

Engine Process function:
  if no commands waiting in player entity input queue:
     player_tick_energy = player_speed / tick_divisor
     if player_entity.energy + player_tick_energy > 0 then return "Hey I need input!"
  otherwise // much better than else
 
  pending_list = new list (or clear old one and reuse each tick)
  foreach entity in actor_list:  // actor_list includes anything that can act (mobs/some items/traps/unstable walls/etc)
    add entity.speed / tick_divisior to entity.energy
    if entity.energy > 0 then add to pending list

  pending_list.Sort( on energy descending ) // highest energy levels first
  foreach entity in pending_list:
    do something and adjust entity energy level by subtracting cost of something action
    // this is where we would've run into the stall problem if we hadn't made sure the player entity wouldn't hang

  clean up and return


Simple.

Hope this helps,
Brian aka Omnivore

PS: There is a slightly more complicated, improved version that handles a number of possible additional cases, as well as ensuring that every action that could be taken before player stall is taken before halting.  In C# it could be done using a custom struct that supports IComparable<T> in place of the raw entity for the pending list.  The custom struct holds the entity.energy + entity_tick_energy in an additional field (that is sorted on).  This allows any entity to abort the current process function without causing an unstable state.

PSPS: Slight error in the divisor calculation, the largest speed add divided by the divisor should be smaller than the lowest cost action.

3

Programming / Cached Supercover Field of View algorithm

« on: March 25, 2015, 02:31:49 PM »

Since I keep mentioning it in various contexts and at least one person has expressed an interest in it, here it is.

Cached Supercover Field of View algorithm

The cached supercover field of view algorithm is an optimized form of the obvious, brute force, 'check line of sight between origin and each cell in the area of interest' algorithm.  This yields a fully symmetric, zero artifact, result, assuming the use of a 'Supercover' rather than Bresenham, line generation algorithm.

This implementation preserves the invariants of the original but reduces the order of magnitude of the algorithm, increasing performance, by using classic memory for speed tradeoffs and taking advantage of the fundamental nature of the problem space.

Let us assume we have as inputs, a predicate DoesMapBlock(point), a function AllPointsBlockedBy(point) which returns a list of points 'behind' the indicated point, and an iterator SpiralWalk(bounds) which returns an ordered sequence of points from the origin through each point with a square bounding box 'bounds' where the dimensions of bounds are equal to 1 + 2*radius of vision.

We have a feedback predicate CanWeSee(point), and our output is an action WeDoNotSee(point), where the output is a map of booleans initially true for all points.

 For simplicity's sake we will only consider the case where viewpoint is equal to the origin (point 0,0), and we will not consider further optimizations such as quadrant (or even octant) folding.

Our field of view algorithm becomes simply:

Code: [Select]

for each point in SpiralWalk(bounds):
      if !CanWeSee(point):
        continue
      if DoesMapBlock(point):
        for each blocker in AllPointsBlockedBy(point):
          WeDoNotSee(blocker)

Both CanWeSee and WeDoNotSee are trivial lookups and get/set operations on a map of booleans initialized to true.  DoesMapBlock is application dependent.  SpiralWalk is just an iterator over the perimeter points of a rectangle where the rectangle is inflated by two in each dimension each cycle.  AllPointsBlockedBy is a lookup into a map that returns a list of points 'behind' (alternatively blocked by) the indicated point.

In order to construct the map consulted by AllPointsBlockedBy, we can create a universal map for a given maximum radius by evaluating each point in the bounding box described as having dimensions 1 + 2 * maximum vision radius.  We evaluate by iterating over the points generated by a Supercover line generator from start = origin, to end = each point in bounds.  Each point evaluated will be associated with a map of booleans that is initially set to false.

The basic cache generation algorithm is:

Code: [Select]

let cacheMap = map of list of points with map dimensions bounds
for each point in bounds:
  let evalmap = map of booleans with dimensions bounds initialized to false
  for each lineEndPoint in bounds:
    for each linePoint in GenerateSupercoverLine(origin, lineEndPoint):
      evalmap[linePoint] = true
      if linePoint == point:
        break
  for each evalPoint in bounds:
    if (!evalmap[evalPoint]):
      cacheMap[point] += evalPoint
The function AllPointsBlockedBy in the field of view algorithm then simply becomes 'return cacheMap[point]' for any given point.

There are a number of further optimizations that can be made.  Most notably, the size of the cache can be greatly reduced by quadrant or even octant folding and each evaluated point can be compressed to a pair of bytes or less for most roguelike purposes.

The iterator GenerateSupercoverLine used above is assumed to be a partial supercover variant based on Eugen Dedu's description of a modified Bresenham algorithm found at http://lifc.univ-fcomte.fr/home/~ededu/projects/bresenham/  The partial variant ignores exact crossings.

The most significant drawback of this algorithm, other than the increased memory requirements, is that it is only suitable for cases where a boolean result per cell is desired. 

Hope this is of interest,
Brian aka Omnivore

PS: Why Supercover and not Bresenham?

4

Design / Wargame+Roguelike+Terminal=???

« on: March 22, 2015, 02:46:56 PM »

  Ok, my art skills are lacking even for hacking 12x12 fonts 

Anyhow, I'm wondering if anyone has done this and if they have some decent fonts to share?   For something like cp437 it only requires replacing two glyphs, of course it works best with square font sizes.  It is a bit expensive on real estate in a terminal, basically you need double the number of rows and columns.  I don't expect that to be much of a problem on anything but mobiles.

5

Programming / Dataflow programming in roguelikes, exploring Field of view calculation

« on: March 14, 2015, 03:13:39 PM »

Dataflow programming in roguelikes, Field of view calculation

This is one of those, probably YAGNI yet fun, off the wall learning experience/sidetracks in roguelike programming.  Not only revisiting Fov calc, but doing it with an eye towards uncovering any hidden opportunities for producing friendly, simple, easy to maintain, and parallel processing friendly, code using a seeming unrelated (to roguelikes) technology: data flow programming. 

In a Fov calc, the input is a set of cells containing information about visual conditions, the output is a set of visibility values, one for each input cell.  Input cells conceptually contain an additional value, their location (x, y).  The bounds of a Fov calc's input is a square of 2r+1 dimensions where r is the maximum observation distance.  In regards to the distance, there are three distinct sets, the outer zone [outside the bounds], the inner zone [inside the square described as r' = r * 1/sqr(2)], and the contested zone described as the intersection of bounds with not(inner zone).  Regardless of actual Fov algorithm used, the conceptual Fov calculation can be simply described as a set of rays emanating from the center, viewpoint, cell and radiating outwards to intersect each and every cell along the path to each cell (ideally).

At the origin cell, viewpoint, the output is dependent entirely upon the values contained in that cell.  For other cells, the output value is dependent upon not only its own data, but that of each and every cell from, and including, the origin to itself along the line between them.  A naive implementation has an algorithmic complexity of O(n^3) and a data dependency of 1 + 2*d (where d <= r) input cells per output cell.  If we encapsulate the entire Fov calculation in a single transform, we have a simple dataflow model of: in => transform => out.  Call this model A.

The nature of the dependencies noted in examination of the naive implementation suggests splitting the input set into n dependency sets and using one transform block per output cell this yields a dataflow:  in => decompose => transform(xN) => compose => out, where decompose selects between 1 and 2*d input cells per  transform, there is one transform per cell, and the compose operation simply maps each result into a single cell in the output.  Call this model B.

Another way of splitting up the input data is to consider the nature of the Cartesian plane with the viewpoint cell at the origin (0,0).  This immediately suggests spitting into quadrants, and upon further examination, octants.  The dataflow in this model is: in => decompose => transform(x8) => compose => out. In this model, compose is the inverse of decompose and there are eight transform blocks.  Call this model C.

So far, we have only considered transforms whose input is directly derived from the input set.  For very small values of n, model A has the advantage of simplicity.  For larger values of n, model C has the advantage of exploiting the inherent parallelism of the Cartesian plane mathematics and can be easily  implemented using practically any existing Fov calculation algorithm.  Model B seems to be nothing more than a useless observation.  Its only advantage is that its transform operation is inherently simple and presumably fast.  If we  introduce the idea of feedback however, the picture changes.

It is the nature of the Fov problem space that a vision blocking cell close to the origin blocks (or shadows) all the cells 'behind' it.  Indeed one very  popular Fov algorithm (shadowcasting which incidentally can be simply mapped to model C above) is based upon exploiting this fact.  In model B, if we  organized the selection of the 'next transform to run', we could potentially use the output of each transform to prune the available inputs.  This new model can be described as: in => decompose => select => transform(x?) => compose  => out; where transform's output also loops back to be an input to select. Call this model D.

Implementing model D.

Why?  Because A is too simple, C is too easy, and B in its natural form is too naive.  More seriously, the model D has the potential to not only adapt well to parallel processing, but to be also relatively easily expanded to include more sophisticated visual effects such as obscurement and at least the first stage of a lighting model.  Plus its a neat way to learn more about data flow programming.

Our input is a radius value, a viewpoint coordinate, and a map structure which can be queried for characteristics at a given coordinate.  Our decompose block might as well deliver its results in an ordered fashion and select only those points which fall within the given radius of the viewpoint.  Since we want to take advantage of feedback, we want to deliver the cell coordinates in an order that reflects the importance of the cell in its potential to shadow off a number of cells.

Let's start off by creating three bounding box rectangles, all centered on the viewpoint.  The outer bounding box contains all the points that might be seen.  The inner bounding box contains all the points that would be seen if there was no sight blocking impediments.  The third box is the current vision scope bounding box, initially it will contain only one point, the viewpoint.  We will require a PerimeterMarch function that given a rectangle will deliver a sequence of unique coordinates that completely describe the perimeter.  After each call, we will inflate the size of the vision scope bounding box by one (in each direction).

Until the vision scope bounding box is no longer contained within the inner bounding box, we can ignore any distance calculations.  For the portion of the decomposition where the vision scope is larger than the inner but less than or equal to the outer, we will do a distance check for each coordinate before passing it on or discarding it.  That pretty much takes care of the major points of the decompose block.

The selector block is a filter.  Initially the 'thy shall not pass!' set is empty, and it just passes everything along to the next available transform block.  Things get more interesting as each transform block completes.  The output is copied and fed back from the transform block to the selector, then the selector does some voodoo and the 'thy shall not pass!' set is modified (or not) appropriately.  Pretty simple huh?

Ok, seriously, computing the necessary modifications to the 'thy shall not pass!' set is a non-trivial calculation.  We really don't want to do it at run time, at least not for each and every blocking output from a transform.  The mapping can be precomputed, folded, spindled, mutated and stored as a binary asset.  Indeed it can even be a 'one size fits all' mapping that works for any reasonable radius.  The size required, assuming we take the easy way out storing quadrant one and a fixed sized result set, is R^2 * (sizeof(coordinate) + sizeof((R^2) bitmap)) where R is the maximum radius you'll ever use.  For R = 10, with allowance for overhead it's a trivial 2KB+change, but woah, around 320KB for R = 40.

For larger sizes, you'd probably want to go to octant mapping and use variable size, offset, bitmaps.   I kinda skipped a step, at some point we need to generate a partial supercover line from viewpoint to each point coming out of the selector.  Exactly when we do this is dependent upon what data model we're using.  Its the same line that model B delivers straight from the decomposer.  The choices are whether ornot to deliver just an array of points or to combine the coordinates with the map data and delivering that to the transform block.

The exact form of the data given to the transform block may have an impact on performance depending upon processor cache size and other hardware details as well as the size and nature of both your map, the exact nature of your transform function, and, of course, your language of choice.  Simplest and safest, would be to be lazy about line generation and do it in a separate 'preprocessor' block sitting between the selector and transform blocks.  As for the map data, best solution is probably to create an immutable copy of the relevant map data early in the decomposition block and share that with all the transform block instances.

Hope this is of interest and looking for feedback,
Brian

6

Programming / Peanuts - a simple data driven ECS library for C#

« on: February 13, 2015, 04:27:39 AM »

Just finished testing it and getting it up on github.  Documentation is sparse, samples are non-existent until after I incorporate it into my latest roguelike project.  It may, or may not, be of interest, but here it is: https://github.com/Brian61/Peanuts

Enjoy,
Omnivore

7

Programming / Odd behavior of ReadConsoleInput (Windows 7)

« on: August 18, 2014, 10:56:08 PM »

Ran into an strange problem, managed to work around it, but research of various MSDN references and a few hours of googling resulted in no joy. 

The behavior is with key events where a control key is held while pressing an alphanumeric key, the record retrieved via kernel32's ReadConsoleInput shows AsciiChar (or UnicodeChar) set to 1, the virtual key member set to the VK_XXXX value of the ascii key, and the control state member set to the bit for the control key pressed. 

This is decidedly odd to me, and results in a rather hackish handling of what seems to be an unnecessary case.  Has anyone else run across this?  Any idea on why it is done that way?  Did I miss some easy fix that would deliver the more expected result of seeing the actual character representation in AsciiChar (or UnicodeChar) member?

8

Development Process & non-technical / Copyright and Licensing: Nothing to fear but fear itself?

« on: August 07, 2014, 05:49:30 AM »

This subject arose once again in another thread http://forums.roguetemple.com/index.php?topic=4250.msg39076#msg39076.  It leads me to wonder, how many developers here are seriously concerned about this topic in their daily work?   

I believe there are two inter-related issues: one being the legality and financial repercussions; the other being the morality and social reputation repercussions. 

In regards to the first, I am of the opinion that we are 'below the radar', that is, we are very unlikely to be sued or subject to an injunction in the breach.  Even if we engaged in blatant copyright violation, the violation would need to come to the attention of the copyright holder, the copyright holder would have to have the financial means to attempt adjudicative remedies, and the perceived benefit to the copyright holder would need to be sufficient to offset the expense.

The second sub-issue, the morality and social reputation repercussions is, to me, the more important and relevant one.  Here though, we run up against the very definition of copyright and how that concept applies to computer software.  Is a port of a work from one language to another a copyright violation?  What if only the external interface is copied?  At what point does refactoring and customization no longer qualify as a copyright violation?  How can we tell the difference between a copyright violation and an original work addressing the same problem space? 

Lawyers and other legal experts aside, what do we as a community of software developers consider protected by copyright and licensing derived from copyright?

9

Programming / FoV and LoS with obscurants (smoke)

« on: July 02, 2014, 11:05:34 PM »

Adding partial obscurants such as smoke to a roguelike map.  I'm looking at the following algorithm to compute a ray (Python generator form):

Code: [Select]

def generate_ray(grid, ptA, ptB):
    rem = abs(ptA.distance(ptB))
    last_pt = ptA
    for pt in ptA.generate_line(ptB):
        vis = grid.visibility(pt) # visibility factor [0.0..1.0]
        yield pt, vis # return pt and visibility info to the caller at each step
        rem = (rem - abs(last_pt.distance(pt))) * vis
        last_pt = pt
        if rem < 1.0:
            break

In the above, grid is some level map that is indexed by a point and has a method returning the visibility factor of the cell with 0.0 being fully opaque and 1.0 being fully transparent.  Obviously the code is not optimized.

Which FoV algorithm would be most suitable for modification to exhibit the same general characteristics as a ray casting FoV generator using the above?

My initial guess is that a recursive shadowcaster variant could be work, although splitting the cones becomes more complex.

Thanks,
Omnivore

10

Development Process & non-technical / Online social roguelike

« on: June 16, 2014, 07:42:54 AM »

Hard to find a good name for this concept that doesn't evoke misunderstandings. 

We have roguelikes that are played through telnet sharing with central bones and scores.   We have at least one roguelike (ToME) with built in chat channel.  Then there are the roguelike MUD/MOO games, at least one (Wayfar) that I'm aware of.  These are the successes.  Then there are the, well put bluntly, failures, the many attempts at multiplayer roguelikes that have never gotten very far. 

What about combining a persistent coffee player roguelike (short sessions) in a MUD-like text adventure overworld, with a chat lounge and various other MUD social niceities?  Shared bones files of course, perhaps other ways of leaving evidence of your passage for others to encounter?  How about being able to save logs of your session and share them with others? 

I'm thinking of a science fiction theme; a lost fleet (Battlestar Galactica etc) taking the place of a home town.  A MUD/Text Adventure/MOO like star system navigation interface taking the place of a world map.  A coffee break flavored (DoomRL-ish) roguelike game for exploring points of interest such as abandoned? asteroid bases, habitats, underground planetary bases, etc.

Your character would persist between 'serious' play sessions of dungeon delving, you could hang out in the MUD lounge chat with other players, share replays of your mission with others, watch replays, etc.  Players could (hopefully) participate in creation of new content, perhaps entirely through an online building interface. 

Thoughts?  Oh and first time poster here, been lurking awhile, and only have one somewhat playable roguelike to my credit: Snapshot https://bitbucket.org/blprice61/snapshot - hey it has grenades lol.

Brian aka Omnivore

[EDIT: woops had wayward and wayfar mixed up sorry]