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 - naughty

Pages: 1 2 [3] 4
Programming / Re: pedantic object oriented question
« on: April 12, 2013, 02:12:15 PM »
So what's a better intuition to use, then?

All other things being equal you put the method where the relevant objects are in scope. So in the running example of moving a critter, the relevant objects are the other critters and the cells you could be moving over or through. The place they are owned is the map so put the method there.

Like all coding guidelines there's pros and cons. One of the cons is that you can end up with very fat classes with lots of methods and variables if you aren't careful.

Have you actually implemented movement like that? It doesn't sound logical. Game objects move, not the map. Objects move on the map and it ok to get data from the map to objects so they can see what kind of tile is there etc.

Yes, ever since I was taught this and many other things by a grey beard programmer many moons ago I've done this kind of thing on several projects. It does seem to make the code more robust but it does cause some gasps of disbelief from other programmers. I've also been lazy and not followed this guideline and I end up regretting on but small and trivial programs.

I like to think the reasons I've given for putting the method in the map are pretty logical. In fact I would say it's more logical than the natural language noun and verb intuitions commonly used. If you've ever looked into relational database normalisation the ideas have some overlap.

A move() method on the map doesn't mean the map is moving but that the map is moving things (which it owns). Also because moves can conceivably fail (wall or critter in the way) it's more of a request than an imperative command. So a more descriptive (but less pretty) method signature would be tryMoveCritter(critter, x, y) : bool.

Programming / Re: pedantic object oriented question
« on: April 12, 2013, 09:49:26 AM »
Hmm. I'm curious: if the critter object doesn't know its map, then what do you do with something as basic as this: movement. Suppose your "Critter" object has a "move()" method, which, well, makes the critter move. Seems reasonable, no? But then you have to check for walls, etc. (you don't want your critter to move through the walls (unless it's a ghost or something)!) which means you need access to the map. Plus, if the map contains a reference to the critter attached to the tile it's standing on, that needs updating. So what should one do? What should that call to "move()" do?

In that particular design the move() method should be in the map rather than the critter because the map is the only object with the required context to actually perform the operation. The only way the critter could really know how to move is by accessing the map anyway (by a cached map reference in the critter or the map being passed as an argument to an update() method).

This doesn't occur to a lot of people because standard teaching of OOP is just hideously bad. The focus on the intuitive real world concept of objects just leads to tears in the end. Intuitively it feels like the move() method should be on the critter because critters move but that's not how you should decide where methods live.

Because a critter can't stand in the same cell as other critters you need more contextual information about how to perform the action (i.e. where the other critters are). Also a move can fail for reasons beyond a critter being in the way, e.g. lava, walls. The only place where all the data is at hand is the map object, so move() should go there.

Programming / Re: Graph Grammar and Voronoi based Dungeon Generation
« on: April 07, 2013, 08:15:33 PM »
Jo: The idea is to make a fairly simple, single hit point roguelike but try and push level gen and decoration a bit.

I was part of a discussion at the IRDC in London when I was on the side claiming that roguelike level gen should be more ambitious. So I thought it was time to put up or shut up.

Programming / Re: Graph Grammar and Voronoi based Dungeon Generation
« on: April 04, 2013, 01:02:59 PM »
Actually Krice do you have any examples of the blob plotting system you mentioned? I think I may have misunderstood what you meant,

Programming / Re: Graph Grammar and Voronoi based Dungeon Generation
« on: April 04, 2013, 11:20:57 AM »
Quendus: I'm not too bothered about inconsistent roughness if it makes sense, e.g. water, trees, natural rock formations. As you said though the walls are incongruous. I'll try out the noise on the hex points and I've got a few more ideas since you pointed it out to me.

The force-base graph drawing is by far the slowest part of it all (2-3 order of magnitude). In comparison the  subgraph isomorphism algorithm used to find the patterns has exponential running time but barely appears in profiles. It takes only a few seconds for up to 30 rooms, but 100 rooms took two minutes and 95% of the time is the graph drawing.

At least force-based graph drawing is simple to implement though :^) If anyone knows of a better graph drawing algorithm that would be cool. I've already looked into Tutte embedding and that doesn't really work, some of the planar graph drawing algorithms force everything into a big triangle which isn't any good either.

I found the secret to making the graph drawing work is to apply the force draw after each substitution step (which is very slow relatively). I also have to make sure the inserted part of the graph isn't too tangled up by using an edge from the matched part of the host graph to transform the substitute graph (this roughly rotates the substitute graph into the right position). You also have to prune the potential subgraph matches so only rotated matches are allowed, a flipped match makes it all fall down.

Krice: My previous system used that kind of algorithm, it was hard to get cells out of it though which is why I changed to Voronoi. I also wanted a level of control over the structure of the levels, hence graph grammars. Although the Space Colonisation algorithms I've seen recently might be a good idea as well.

Programming / Re: Graph Grammar and Voronoi based Dungeon Generation
« on: April 04, 2013, 07:25:01 AM »
Quendus: Thanks for the kind words. The walls are irregular because of how I fill the empty space between rooms and corridors. I am considering something a bit more controlled though. It's worth noting that I used random walk hexgrid rooms because they look nice for the demo but I also have room gen based on square grids and randomly assigned points. I just need a set of point for the voronoi to work.

Gameplay wise the idea is that you can walk to any connected cell (any cell that shares an edge with your current cell). Not sure if I'm going to have wall destruction but it wouldn't be hard to support. I've got used to the stained glass look of voronoi so thanks for bringing it up, more consistent walls would look better.

george: Thanks! The visualiser for the level generator is actually how it works under the hood, I'm using Force-based Graph Drawing. As I said above the hexgrids are purely to make the demo look nice, I have other room gen styles but I got impatient to make the video.

There's been loads of inspiration:
  • Graph Grammars came from Automatic Generation of Dungeons for Computer Games by David Adams. The paper doesn't mention how to actually render the graphs it produces. Which is the main bit of work I've added.
  • The idea to use voronoi came from IRDC 2012 in London where I showed the previous tech I was working on. Just after I did the presentation the projector had a screen saver that looked a bunch of voronoi cells.
  • My previous tech was mentioned on an IRDC Roguelike Radio episode and it was remarked as looking 'spiderlike' and the maker of Hyperrogue made a comment about "it'll look fine after you make cells from it". I wasn't planning on doing that at the time but he was totally right and it encourage me to try.

Programming / Graph Grammar and Voronoi based Dungeon Generation
« on: April 03, 2013, 11:00:23 PM »
I made a video of a level generation system I've been working on for a while now. Hopefully not too boring :^)

Here's a screenshot:

Programming / Re: Bosses in a Low Health System
« on: April 02, 2013, 02:44:49 PM »
I think the best bosses have more than one 'phase' to them. So the first phase could be spawning minions, once you've cleared them it starts trying to jump on your head then it starts running after you and you have to make it fall into a pit. The phases could alternate or be one after another with no repeats.

If they have just one set behaviour they feel just like slightly bigger, tougher monsters. You need to really differentiate them to make them really feel like a boss, lots of HP just feels like a cop out.

Another common touch for bosses is to have them situated in some sort of large mechanism or special room. Say you have a boss that fires lightning on all neighbouring cells, you lead it to a 'collector' that is powered up by the lightning and it gives you a single use of a battering ram that is the only thing that hurts the boss. On a similar note it could charge like a Bull and you have to make it hit a spike covered wall to break its armour, exposing its vulnerable fleshy innards.

Other miscellaneous ideas:
  • Large Jelly that splits into smaller jellies and then recombines after a set number of turns. You can only kill the smaller jellies, its invulnerable it its large form.
  • Vampire boss where you attack curtains on the wall to let light in, the light hurts and traps the Vampire until it has nowhere to run.
  • Very aggressive boss that you have to pillar dance. It tires itself out and is vulnerable.
  • Boss that periodically sucks everything in nearby, feed it bombs.
  • Invulnerable Evil Ghost boss in an evil cemetery. You have to kill yourself and attack it in ghost form, some magical force revives you every now and again, rinse and repeat a few times.
  • Frankenstein's Monster, make it look in the mirror so it runs away scared by itself.
  • Giant Slug, Giant Salt Shaker, fight!
  • The Old Hag of the Sea challenges you to a fight in the freezing ocean. Lather yourself with bacon grease before the fight to survive the icy depths.
  • A boss you kill entirely with conversation choices, e.g. 'Is it an African or European Swallow?' or tell a robot a paradox.
  • Pong or Air Hockey against a boss. The puck is an enemy that bounces off you instead of dies when you attack it.
  • Simon Says: the boss does a movement sequence you have to copy, fail and die or succeed and win!.
  • Floor Tiles makes a sound when you walk on them. If you can play out the melody of the background music you win.
  • Evil game show with game related trivia questions.

Programming / Re: L-Systems
« on: March 28, 2013, 09:20:42 AM »
@lithander: Well spotted, I am indeed using voronoi diagrams. I use the graph generation phase to create the room-corridor structure then build a set of points for them. Then empty space is filled and voronoi is run over it all.

There are algorithms for adding connections to sets of points that might help solve some of the issues with L-systems. A previous version of my generation system used Relative Neighbourhood Graphs which are quite simple to implement and will add in potential corridors that don;t cross each other. The self-intersection problem with L-systems is a bit trickier though.

Also I think it's totally possible to mix the ideas behind L-systems and Space Colonisation.

Programming / Re: L-Systems
« on: March 27, 2013, 02:43:24 PM »
One of the issues with L-systems is that they are tree-based (data structure tree not real world tree) and a major feature of roguelike maps and most game maps is inter-connectivity which trees are not really great at. Also they are great for making fractals but it can be a big chore to make the rules to generate good plants. A fairly recent idea for plant generation that seems to have many benefits over L-systems is Space Colonisation. It also seems applicable to level generation or could be used along side L-systems.

If you have a solution for the connectivity issue then try it out, because we really do need some more algorithms and techniques for level generation.

I've been working on a level generation system for a while now that is based on Graph Grammars and force based Graph Drawing, which aren't a million miles away from L-systems. Like L-systems you use a set of rules with left-hand patterns and right-hand substitutions but they are graphs instead of sequences or trees of symbols. This does have the benefit of dealing with inter-connectivity quite naturally but has been a challenge to get working (all algorithms for drawing graphs are really bad for trying to make levels with). The paper that originally gave me the idea to use Graph Grammars is Automatic Generation of Dungeons for Computer Games. It only creates graphs from a logical point of view though, it's doesn't layout where the rooms and corridors actually go. That's the bit I have been working on :^)

Here's some screenshots of levels generated from the same ruleset.

Programming / Re: Structured Enemy Design
« on: March 15, 2013, 08:33:44 AM »
Although the idea is worthy of thought I think there's two issues:

It's hard to properly balance in purely numeric terms. You end up having to add fudge factors into the model to make things actually feel balanced. For example a 1d8 weapon and a 4d2 aren't really balanced (the 4d2 would be noticeably more powerful the vast majority of the time) so what are the general statistics needed to balance them? There was a fad in the FPS industry for balancing based on DPS but it doesn't take into account other factors that go into 'effectiveness' so slow firing weapons end up being underpowered. The designer had to come in by hand and fix it while getting lots of play testing done to guide them.

Also I don't think a smooth difficulty curve is the ideal. You want moments of power and moments of relative weakness in alternation. Roguelikes tend to get this 'by accident' because specific builds will have strengths and weaknesses and random drops have such a huge impact on your survivability.

I think only incredibly trivial games can be mathematically balanced. However if you have a good enough AI system you can run lots of simulations and adjust according to the results, which should be a lot quicker and cheaper than getting lots of play testers.

Programming / Re: Deterministic combat too complicated?
« on: March 13, 2013, 03:46:30 PM »
You can fix the heap issue by using a user-defined < operator or function and having a 'tie-break' value, e.g. an incrementing id assigned to each actor. So if the ticks values are the same it uses the tie-break value to determine who goes first.

You can easily calculate a number of ticks per turn to use given the smallest fraction you want by using a factorial. So if you want to be able to use 1/2, 1/3, 1/4 and 1/5 you calculate 5! which is (1*2*3*4*5) = 120.

To be honest I'd guess that quarter turns would be enough so that's 1*2*3*4 = 24 ticks per turn.

Programming / Re: Deterministic combat too complicated?
« on: March 13, 2013, 12:25:16 PM »
It can be very confusing when the player or enemies get 'out of sync', e.g. if the normal tick rate is 10 and you do a move that takes 5 ticks you can feel that you're out of sync from then on. It can happen in crawl sometimes and I've had it bite me on my own project. This can also be caused by using heaps as a priority queue, they are normally unstable in the sense that two actions that have the same tick counter can happen in either order.

I think it's best to restrict to whole multiples or simple fractions like 1/2, 1/3, 1/4 (so no 3/4 or 2/3). In mathematical terms either the numerator or denominator should be 1. In fact using fractions for ticks is something I surprised isn't really done, it's always integers which causes all kinds of problems if you want an action that takes exactly 1/3 of a usual tick. (I think Brogue uses 100 base ticks per turn and there's at least one action in the game that's supposed to take 1/3 of a turn but 1/3 of 100 is exactly representable. Not a major issue perhaps but it triggers my programmer OCD).

You could remove some of the out of sync issues by forcing actions to always take a whole number of 'big' ticks. So a stance could be modelled as a set of actions that always add up to whole number, e.g. defensive stance move is 1/2 tick movement then 1/2 tick defend (defend is a state that reduces damage say), fast stance is 1/2 tick move, 1/2 tick move (so you get two moves but you aren't defending so take more damage if hit), aggressive stance is 1/2 tick move and 1/2 tick 'prepare to counter' so you can hit back at enemies if they hit you but you take more damage than when defending.

Programming / Re: Deterministic combat too complicated?
« on: March 12, 2013, 11:20:02 AM »
After playing around with the single hit-point model a bit I think the secret to making it work is interesting enemy behaviours. Which is something Darren has always mentioned when talking about it.

For example I have an enemy (a leaper) that when you're two cells away will bounce for a turn, then the turn after will leap to the cell you were at when it started bouncing. So it's quite easy to avoid a single leaper, when it starts bouncing you move away, it then lands on the cell you were just on and is an easy kill.

However if you have two or three leapers in the same room it becomes a lot more interesting. You can even get them to kill each other if you can engineer the situation; you get two leapers to bounce at the same time, then move away so one leaps and lands where you were the then other leaps in and kills the first.

I have a big list of behaviour ideas that I plan on trying out. If it helps you, here they are (very short an simple, not a lot of detail and some reference monsters in other roguelikes):

  • Leave a trail of stuff.
  • Have a cloud or bad stuff surround the monster, e.g. Brogue's Zombies.
  • Attack all surrounding cells.
  • Knight's move. Not sure how that would work in a graph based map though...
  • Only able to move to cells with a distance of 2 from the current cell.
  • Move two cells every other turn.
  • Move very quickly when not in LoS.
  • Obscure LoS.
  • Reset Fog of War.
  • Summon and run away.
  • Summon and consume summons for some kind of bonus.
  • Explode on death.
  • Sap the player at a distance (not allow player movement) and run in for the kill.
  • Become insubstantial and walk through the player.
  • 'Haunt' the player and control movement.
  • Impregnate the player with a parasite that will burst out later.
  • Rotating laser beam, i.e. attack each surrounding cell in an order.
  • Throw nearby enemies at the player.
  • Kill other monsters to 'level up'.
  • Multiply on hit, e.g. jellies or rats in MicRogue.
  • Telegraph attack by bouncing then leap where player was next turn.
  • Telegraph attack with crosshairs on the floor and attack next turn.
  • Mimic player movement directly or oppositely.
  • Buff nearby monsters, e.g. Brogue totems.
  • 'Turtle' and become invulnerable to some or all attacks.
  • 'Ignite' or otherwise transform the terrain the player is on.
  • Steal items from the floor or the player, e.g. Brogue's monkies.
  • Reanimate after death, maybe a few turns lag.
  • After an attack become a fast moving but non-attacking form, e.g. Shiren's Master Hen.
  • Teleport or blink the player.
  • Pull the player closer to the monster.
  • Push the player away from the monster.
  • Swap positions with the player, e.g. Eyes in MicRogue.
  • Try and surround the player with invulnerable monsters that only attack once fully surrounded.
  • Mimics and shapeshifters.
  • Combine like Power Rangers...
  • Disperse 'seeds' like those mushroom things in Crawl.
  • Be invisible unless very close.
  • Temporarily reduce players view distance.
  • Restrict player movement, e.g. can't move away from monster like DCSS's Sirens.

Programming / Re: Replayability
« on: March 01, 2013, 12:44:50 PM »
Achievements don't have to follow the standard model of being online and your friends being able to see them.

For example a roguelike could track your progress and give you some encouragement when you die:

Congratulations You Died! But...

You got 1 level deeper than you previous best!
You beat your average time to the Dungeon of Woe and got there in 1:02.
You killed more than you average amount of Orcs!
You found the Trousers of Virtue for the first time!
You cast fireball 12 times, raising your total to 342!
You got revenge on Gas Flange the Bloated, who has killed you 5 times before.

Pages: 1 2 [3] 4