Tuesday, 22 December 2009

::tap-tap:: Is this thing still on?

Oh! Hi there.

Amazingly, I have been working on this little project. It's been slow going.

The rendering system has been refactored considerably. It is very much still a nasty mass of imperative wrongness, but its also a bit more consistent and less fragile. I've been experimenting with different methods of generating the world geometry. I've tried half a dozen implementations of a game-entity framework, none of which seemed adequate. I added a quick random map generator (screenshot taken from one such random map), and worked on the water shader a little. It looks OK in motion, but definitely needs to be somewhat more obvious generally. Those little divots in the ground are shallow water, the light source being the player (who's mesh has temporarily elected to disappear).

Oh, and I gave Clojure a spin too. Experimenting with the property-bag approach in a Lisp is relatively joyous, especially with Clojure's explicit syntax for hash maps. I found it hard to scale projects up, though. I'm too used to arranging things in terms of objects and classes, both Haskell and Clojure befuddle me with a mass of functions. My failing entirely, the languages have much to recommend them.

I started using Mercurial SCM for source control on this little project. Although I do find myself wanting a P4Win-like GUI front end (which may well exist somewhere), the command-line tools are quite lovely and I refuse to give up on them before becoming at least somewhat proficient.

Now for some design babble. This idea surfaced recently when trying out a few entity and time-handling systems, and I think has some interesting gameplay connotations. Here's the gist:

  • Every turn, collect actions from all agents in the game world

  • Execute all actions, regardless of validity, to produce a new world state. Each agent also tracks the actions that changed it this turn.

  • Resolve the world state by resolving invalid conditions

The third step is obviously the tricky one, but also where the most interesting aspects spring from. The first two steps merely simplify some aspects of mutating the game world.

So this tricky 'resolve' stage... what happens here? Well, take a very simple set of verbs: agents can either stand still, or move one space each turn. More than one agent occupying a space is invalid. If two agents occupy the same space, do some basic conflict resolution and then generate a valid world state based on that. The losing agent could be displaced back to its original position (and also presumably lose some health, in a standard Roguelike game of HP and damage rolls...), whilst the winner occupies the contested space. In the case of a tie, both agents are returned to their starting positions. An agent who didn't move in this turn gets some manner of defensive bonus, but if it loses the conflict will be displaced away from the attacker.

There are immediate problems with this simple method. What happens if another agent occupies the starting position of the losing agent in a conflict? How do we handle three or more agents in a space? What about an agent surrounded by enemy agents, such that no position is valid after losing? Conflict in dead end corridors?

Some embellishments to the system should allow most of these to be resolved. For example, agents could be in a standing or prone state, and not occupy any space when prone. Losing agents with no valid moves can be knocked prone. And so on.

But what do we gain from this approach?
  • Most interestingly, this represents a gateway to yomi, as described in the linked post. As every action is essentially simultaneous, a suitable number of counter moves and counter-counter moves allow for much greater potential depth in conflict. There aren't enough in the simple example above, but it at least admits the possibility. In order to be really satisfying, either the AI behaviour needs to be tractable for the player, or multiplayer might be considered.

  • Strategic positioning - this is a big part of what I'd like to capture in combat. Being able to 'bull rush' opponents is crucial; several character development options suggest themselves to allow more tactical control over the way a battle evolves. This feels a lot easier to approach when all potential movement is handled in a single step.

  • I think this system is less predictable. As everything happens at once, actions are more likely to fail and rather harder to evaluate. Rather than just considering the success chance of a given action, the player must consider all the possible actions of relevant agents that could interfere with its execution. This is a good thing in general.

And what is lost...
  • Agents all move at a uniform speed, or at integer multiples of that speed. We lose the fine-grained ordering of agents based on some intrinsic properties and/or the execution time of actions. All actions take one turn. We can allow for slower agents by forcing them to take null actions except every N turns. In theory we can also allow faster agents by slowing down the rest of the world in much the same way, but that seems inelegant - as many actions will require a graphical representation and time to be displayed, doing this will slow the game for the player.

  • The system is less predictable. Players can no longer easily guess the outcome of an action, as it depends on the actions taken by other agents in the same turn. This could be a bad thing for transparency.

It needs more thought, and the implementation details could get very messy for the semi-mystical 'fix the world' step.


Radio Babylon said...

good to see youre still making progress. i like reading about the technicals behind it, and i hope to see and play a finished product as well someday. looks great!

Jotaf said...

Good read! I think you could draw some inspiration from puzzle games in showing the player the outcome of a turn. RPGs show little floating strings like "*miss*" or "-52" (HP), but in puzzle games there are often symbols such as arrows.

For instance, each move could be depicted by an arrow appearing in that direction (or a shield if the actor stands still), and when that results in conflict, the arrow from the losing part will be red and fade away, perhaps even have a cross appear over it. Winning would be green and simple moves could be white or blue. Symbolic depictions like those are IMO much better than the classical message log of RLs, and the floating text/numbers in RPGs!

Snut said...

I really like this idea! How to represent combat is something I've been struggling with for a while, especially as animation is something I'm really not betting on for first release.

This symbolic system sounds far more interesting and easier to 'read' than just sliding some pieces around and doing some damage, and can be elaborated with sound and visual effects easily to make the conflict resolution more interesting if needed.


wtanksley said...

We can allow for slower agents by forcing them to take null actions except every N turns.

Why not slap everything into a priority queue, and then execute the queue up to the first priority change (collecting the resulting interactions into a graph), and then resolving the graph until all conflicts are gone and everything can move?

That way nothing actually changes position until all of the conflicts are resolved; and nothing needs to get processed that's not either actively moving OR involved in a conflict with something moving.

There's no reason to "execute a null action". Unless that winds up being faster, of course. :-)


Snut said...

Hmm, I guess I phrased that badly. Null actions might be useful for logging/debugging purposes, but I was thinking of a very simplistic approach - just skipping those entities.

entites.filter( e =>
currentTurn % e.actionPeriod == 0 )

Or something of that ilk. Helpful side-effecting aside, it doesn't really matter if entities emit actions which just behave as the identity, or we skip them entirely.

At the moment I don't know how different a 'world state' object will be from a simple interaction graph, but it's an interesting idea. I'm certainly not planning on actually moving anything in the rendered representation until a final valid world state has been decided! That'd be confusing...

All that said, I don't have much free time at the moment so the implementation is going slowly. There are probably plenty of things that are going to prove annoying or ugly, and maybe just stating the problem differently will be very helpful.

Thanks all!

wtanksley said...

Snut, if you scan through all entities and skip some of them, your running time will be linear in the number of entities, which means that you'll want to either limit the number of entities or the granularity of your time system (which in turn means that everything's going to move at roughly the same speed) lest your system become too slow.

I'm suggesting that rather than scan-and-skip, use a "heap queue" or "priority queue" data structure, which will allow you to process only the creatures which actually are scheduled for a turn right now, and totally ignore the others. Not only will you save time by not processing some, but your running time changes from linear to logarithmic, which is a decent savings if you have a lot of entities to process.

I don't know what language you're using, so I don't have a suggestion for a library -- but it's a fairly simple data structure.


Snut said...

Ah! I see what you mean now, sorry.

I don't think it's necessary, however. For one, I'm only intending there to be a few hundred active entities at most. I'm restricted to small levels at the moment due to the time required to generate the terrain mesh, and I was always intending to use relatively few enemies and try to make small-scale combat more interesting. Traversing the list will be a trivial cost, I suspect any bottleneck in this area of the code will stem from the AI generating actions. I'll optimise that bridge when I profile it, to abuse a phrase.

For two, the coarse granularity of the system is a benefit in many ways. In order for the simultaneous movement to actually produce interesting gameplay, it has to occur predictably. I think that the concept of 'slow' entities (intrinsically or as a result of temporary effects) only getting to act every other turn is quite transparent. Maybe certain actions could also cause entities to 'skip their next go' in true boardgame tradition. Fast entities can probably just be allowed more exotic movement actions rather than breaking down the turn system further.

Although I'm not certain, I think such a simple setup will be sufficient for adding depth without too much complexity, and shouldn't be hard to signal to the player in a clear way.

But if it turns out to be too simple a model of time, or I end up dealing with many thousands of entities, I'll definitely need to revise the approach.