• Advertisement
  • entries
    16
  • comments
    19
  • views
    17034

About this blog

documenting and motivating my attempt to make a simple roguelike RPG

Entries in this blog

Update #16

No progress on the game. This sudden stop to any game development happened because I ran into performance problems. I focused on writing my code OO and as a side effect it is very poor in rendering performance. I realized I needed to find out the best way of render a tilemap, rendering particles, etc before making a game. Things like spritesheets/atlases and vertexbuffers and hardware instancing.

So I stopped developing the game and started to read more stuff online, try out examples and benchmark on my machine. The most useful thing is to read people's past questions on gamedev forums and the like and read the answers they are given by people who know what they are talking about. Even questions which I didn't think of asking provide answers that are useful to know. It saves time having to write a benchmark and test things if someone who knows can give the answer. One trap to bear in mind when doing this is that answers can become obsolete over time as the APIs change. Stuff that used to be inefficient can become efficient and stuff that was important to do for performance can become irrelevant.

Anyway back to the game. I am scaling back massively my overly ambitious plans. I now plan to make a very simple roguelike, no massive map, just a traditional small map for each level of a dungeon. Really I already have this largely in place before I got side-tracked on very big virtualized maps. As a benefit the performance requirements for small maps are even lower. I'll try to get a very simple first game done before trying anything too complicated.

Performance

I might as well mention the performance problems I hit in the current game. I have a Tile class and it has a Draw() method. In that method it calls DrawUserPrimitives to render a quad for the tile. The Item and Monster classes also have a Draw() method and do the same thing. This is nice and OO, but rendering a 50x30 tile map results in at least 2500 DrawUserPrimitives calls per frame. Stupidly inefficient for what is largely a static map and could be rendered in a single call.

It's kind of okay, hardware is a bit more advanced these days than 10 years ago. On my machine I can render 100,000 textured triangles at 11 FPS which sounds bad, but now consider I am making 100,000 calls to DrawUserPrimitives each frame, one for each triangle. If I instead render in batches of 10,000 triangles (so 10 DrawUserPrimitives calls), I get about 220 FPS.

Some thoughts:

  • What matters? Doing it "right" or getting it to work? So what if the rendering is stupidly inefficient, if it renders at 60FPS on any modern PC or laptop who cares?
  • I am making a turn-based roguelike with exceedingly low graphical requirements, not some cutting edge FPS. I can sacrifice a lot of efficience.
  • Does improved performance really require breaking OO purity or can I do OO differently?

    For the last question I thought it should be possible to insert my own caching/batching layer between the game and DrawUserPrimitives. Still working on it but so far it doesn't perform as well as I hoped.

    As a side note I am going to the International Roguelike Development Conference in London at the weekend as a noob looking to learn from people who know what they are doing.
    http://roguebasin.ro...x.php/IRDC_2012
    *Anyone who is confused why I am not just using spritebatches in a 2D game, I wanted to learn 3D rendering even though I am making a 2D game.
I haven't made zero progress, just unseen ninja progress. No screen shots possible, so sorry this will just be a big chunk of text.

The main change I have done is adding support for an infinite tile world. I divided the world map into 32x32 tile chunks and introduced a 3 stage cache along the lines of Disk -> RAM -> Video memory.

What I was doing before was rendering each tile in a separate DrawUserPrimitives() call. This was fine for a dungeon it seems, but for an outside world in which I want to be able to zoom out quite far...well 100x100 tiles = 10,000 batches each frame which is just stupid. I got slowdown on my card when zooming out a fair distance, although admittedly my card isn't a particularly fast piece of hardware.

What I am doing now is using a VertexBuffer. When a map chunk comes into view I load it's vertices into the buffer. The vertices's are then kept in the card memory and I don't have to pass them all to the card each frame (at least that's how I think it works..still learning this stuff).

The VertexBuffer is big enough to hold about 25 map chunks. That's more than enough to cover a large enough area if the player zooms out. From what I've read it's a bit expensive to set data in the vertexbuffer, in fact I've read people saying don't set data in the vertex buffer during the game, only do it during initialization....well ok but I couldn't see any other way. So as the player moves across the map the older chunks in the vertexbuffer are replaced.

The RAM cache is for chunks that used for a non-drawing use, eg calculating a line of sight in a distant area. It would be bad to load a chunk into the vertexbuffer that wasn't even going to be drawn. I suspect there will be a lot of processing of non-visible chunks.

The disk cache is what enables the "infinity". The RAM cache is limited in size and reads/writes chunks from the disk cache as needed. It seems to work smoothly enough. The Map Generator itself has no concept of chunks, it just writes terrain in tile coordinates. Behind the scenes the necessary chunk is loading into the RAM cache and the tile modified.

Tile Textures

Textures are a big problem now. Before when I was drawing a single tile at a time it was easy (although very inefficient): I would just set a different texture depending on the tile background before the draw. Now I am drawing 32x32 tiles at once and some of those tiles could be grass, some could be rock, etc.

What I am currently doing is having a big sprite sheet texture, well it's not that big - 512x512 at the moment which holds 64 64x64 tile textures. Then for each 32x32 map chunk I have the vertex texture coordinates set to correct offsets into the sprite sheet to pick up the right terrain type for each tile. A problem is that texture cordinates are proportional and not absolute so the offset into pixel 64,64 of the sprite sheet is 0.125f, 0.125f which threatens precision problems. It can be dealt with but it isn't great.

Another possibility I might try is to pre-render each chunk to a single texture and save that to disk, then load that on the fly using a similar disk->ram->video memory cache system as used for vertices. Unfortunately that means more loading of content during the game. On the otherhand having a single texture for the entire chunk means I don't need to draw a chunk as a 32x32 grid of triangles anymore, it can be a single quad. Kind of negates the need for the vertex buffer...

So yeah you can see I don't know what I am doing. Still reading/experimenting trying to understand how video cards work and what i need to worry about in terms of performance and what I don't. Mainly trying to figure out the traps (Eg here's one I fell into: http://www.altdevblogaday.com/2012/02/05/dont-store-that-in-a-float/). I guess it was a stretch to imagine I could just "make a game" without the overhead of having to read stuff. Maybe my 2nd game will go faster.

Field of Vision

This is about field of vision in roguelikes. You are looking down on the dungeon/world and yet certain tiles are not drawn because even though you can see them from above, your character cannot because eg a wall is in the way. This is different from line of sight. This is about calculating an occlusion mask that is drawn over the map for areas your character cannot see.
I disabled field of vision as soon as I switched to a surface world map because my inefficient implementation that could only just cope with small dungeons failed miserably with wide open spaces. Calculating whether each tile on the screen is visible to the player's tile each frame was too much.

I could spend time understanding and implementing one of the more modern fancy algorithms.
http://roguebasin.roguelikedevelopment.org/index.php/Field_of_Vision

But I am lazy so I started thinking if field of vision was worth it. Inside a dungeon yes it is, somewhat. But outside...I think gameplay would work without it. A maximum radial view distance works fine. Creatures could still be hidden if they were out of line of sight.

/longwinded unformated update
To recap: you start in the south of the game world and the objective is to reach a location in the far North. To get there you must pass through unique zones with different challenges: a desert zone, a dense forest zone, an icy mountains zone, a swamp zone, etc. Each zone is harder than the last - both in terms of the monsters in it and the environmental dangers. Here's a rough diagram of the world map and the different zones that must be crossed:

mapzv.png

The zones themselves and the order they occur in the map will be fixed in every replay of the game, but the contents of each zone - the placement or rivers, monsters, trees, etc will be different each time to increase re-playability.

The North/South dimension of the map is figured out, but the East/West options are open:

  • Thin map. The player is prevented from traveling very far east or west. This will seem somewhat unrealistic but will increase the challenge. The thin map limits the paths a player can take North and will force the player to sometimes *have* to pass that difficult monster/obstacle.
  • Wide map. Width of map still limited but the player has more choice of paths to take North. This means the player can avoid tough challenges, retreat and take another route North. A wider map also increases the explorable content of a zone.
  • Infinitely Wide Map. The player can travel infinitely east or west. Map generation would have to be on-the-fly. No "unrealistic" physical barriers.
  • Looping Map. If the player travels far to the East they eventually come back to where they started. Advantages: No physical barrier to east and west is required and the map can be pre-generated. The big disadvantage here is that a looping map is harder to implement and lots of edge case (literally) testing must be done to avoid catastrophic bugs.

    I'll probably avoid the exotic "infinite" and "looping" solutions and just make a limited width map of configurable width. I can always change this later right? Lets see what the gameplay is like before deciding this.

    Plains Zone

    Each zone has very different content. The desert zone for example won't have rivers, while the forest zone will have occasional rivers and a lot of trees. The lake zone will have loads and loads and loads of water and perhaps a few islands. It makes sense for there to be a separate generator for each zone, so I have decided to focus on the generator for the plains zone to begin with.

    What is in the plains zone? The plains zone is where the player starts. It is meant to be the easiest zone. Here's an image depicting my initial idea of what plains zone will look like:

    map2z.png

    • Lots of grass with clusters of trees.
    • East/West rivers with occasional bridges or fjords to cross them.
    • Small lakes/ponds.
    • Large rock outcrops containing caves.
    • Villages or huts (not sure if they will be inhabited).
    • In this zone there would be a lot of food/water available and other resources.
    • The above image is only a small amount of the zone's height extent. The actual zone would go on much further south/north than the above image. It would take the player many game days to cross a zone.
    • In the South of the zone the monsters would not be very threatening (small wild dogs, foxes). Further North some of the caves might have a defensive bear in them and there might be the odd wolf about during the night. Even further North there would be large dangerous bears roaming about during the day and packs of wolves at night.

      Constraints

      Take a look at this map and imagine it was procedurally generated:

      unwinnable.png

      There's no route North. The player must cross the river, but there are no crossing points and the player has no boat. A wider map reduces the chance of such an obstruction happening. A longer zone increases the chance. In any case the game map generator must never create cases like this.

      There are three solutions I thought about for guaranteeing a zone will be passable:

      1. The generating algorithm has the responsibility not to create impassible output. This is quite hard and it is prone to error. I don't want to have to (ie can't) mathematically prove an algorithm won't create impassible output.
      2. Test each zone the generating algorithm produces. If it's impassible then chuck it out and generate a new one. This solution works, but in dense zones there could potentially be a lot of chucking out and processing time spent testing maps.
      3. After generating the map, trace one or more random North/South paths through it. Either go round obstacles or destroy them.

      I'll probably go with solution #3. It guarantees a path through the map and doesn't require an exhaustive test. Here is an example of 2 guaranteed paths being created through the map:

      winnable.png

      This is adequate for the plains zone where the obstacles are sparse. In the remote chance of an obstructive barrier as above the player can easily hunt east and west for the path through. For more denser zones (eg thick forests) this solution will not be adequate as it will lead to the creation of Mazes with numerous Dead Ends and only a few solutions which are frustratingly hard to find. The player may have to backtrack miles back South to get back to the right path. If they have to do that the game has failed.

      The solution for denser zones will probably be to divide the zone into a grid and make sure each neighboring grid tile has a short connecting path. Ie to trace paths horizontally as well as vertically.

      Pre-Generating vs Generating On-The-Fly

      The main benefit of on-the-fly generation is to support infinite maps. I have decided not to have infinite maps so the only remaining benefit of on-the-fly generation is to reduce pre-generation time at the start of the game. However that's not really a big deal. It's a once-only task which takes a relatively short amount of time compared to how long you will be playing in that world. The disadvantage of generating the map on the fly is that the map generation algorithm gets more complicated.

      So I will stick with pre-generation for now. I am actually a fan of world generation at the start of the game. It makes it seem like something cool is being made for you to play. The generation at the start of Dwarf Fortress where it creates the world and it's history is pretty cool.

      Also weirdly I like the idea that the game world exists in it's entirety. Far far to the North there are already structures set in stone. There might be a terrible monster on the map somewhere. There's something cool about being able to (in the debugger at least) ask where that monster is. In contrast knowing that the world is being randomly built as I travel makes it seem less real. Although from the point of view of the player it makes no difference of course.
I have come up with the rough idea for the game. Gameplay will take place almost entirely on the surface. I made a quick prototype that gives a very rough idea of the kind of top-down terrain view the game will take place in. Ignore the lighting/textures/framerate...and in fact the gameplay...

[media]
[/media]

The actual plan for the game (which isn't really shown by the video) is:

  • Pre-historic wilderness setting.
  • The objective of the game is to travel to a place far to the North. There will be some weak plot excuse to justify this, but that doesn't matter so much.
  • The further North the player goes, difficulty will increase. So it's like a sideways version of traveling down into a dungeon.
  • There won't be level transitions, the map will be continuous and loaded as needed.
  • Permadeath. If you die you can't reload. Your score is how far North you get.
  • The game is about survival, not hack and slash. If you can make it north without fighting a single monster (you won't be able to) then you still win.
  • As you head North you will have to cross progressively harder environments with their own environmental challenges and monsters. The starting zone will be easy, perhaps a warm grassland with few dangers. Further North the zones will get harder with additional hazards. Eg ice mountains, a desert, a jungle, a dense forest, a huge lakes, perhaps even a section where you have to cross underground through a mountain. The zones themselves will be at the same "latitude" north in each game, so the player can have some achievement from just reaching (or surviving) a zone. But the contents (terrain, monsters (placement not type), etc) of the zones will be randomly generated.
  • Monsters will include realistic natural animals, eg wolves, bears, crocodiles, dinosaurs? and made-up ones. No high fantasy creatures like goblins.
  • No magic. I don't see any need. There may be skills like tracking
  • No XP from killing monsters. Kill them either for food, resources, survival or fun.
  • You need to sleep occasionally. A lack of sleep will be penalized (reduction of speed, sight radius?). You decide when and where to sleep. You are vulnerable to attack while sleeping. You can reduce that chance by sleeping next to a fire or in a shelter.
  • You find/construct tools and clothing to help your survival. eg a torch can scare off some creatures, thicker clothing will protect you from colder times/places.
  • Day and night transitions, seasons and weather affect gameplay. Some creatures will be nocturnal. Some creatures will hibernate during the winter. At night it's colder, during winter it's colder, during storms it's colder. If it's too cold you will take damage, to prevent that you either wear thicker clothing, take shelter or build a fire.
  • You can construct shelters to protect yourself from the environment. Simple ones like tents are quick to make but provide minimal protection. Bigger ones like log huts take more time and resources.
  • Different zones have different hazards. For example in a desert thirst is an environmental hazard. The player will need to find or carry supplies of water which will be rapidly exhausted. In zones with plenty of water it is assumed the character can handle thirst themselves. In the mountains storms and extreme cold are hazards.
  • The player is killed for mistakes they can learn from rather than by the random number generator. I can't prevent RNG deaths full-stop but I want to reduce them. The game is about increasing the odds of survival. Doing really dumb stuff will dramatically lower the chance of survival - eg crossing a desert without a supply of water, or diving into a random pool of water in the jungle, or attacking a bear with a stick. Making less obvious mistakes will lower the chance of survival - eg wandering around in a storm wearing metal might just get you killed by a lightning bolt, sleeping in the open without a fire (or even sleeping in the open with a fire if there are human hunters about)
  • The player can balance how fast they head north. They could try to rush. Or they could move slowly through build-shelter/explore cycles. On reaching the lake zone the player might decide to build a boat and risk the crossing, or they might decide to take a very long trip round the lake risking all the shore based predators. Or they may decide to build a really strong shelter, wait for winter and then walk across the frozen lake.
Very unproductive week for the game but I think I have learned something about game development. I wasted it thinking about the UI. Why? The current UI is a mess. At 800x600 resolution with all the various windows open you can't see the dungeon:

stuff2.png

So I was trying to figure out how to reorder it all. What windows do I need? How do I divide it into different screens with shortcuts? Do I need a hotbar? If the user is in a shop does the floor need to be visible? Should the message log be minimal but expandable? etc. I kept hitting the same brick wall - I can't answer a lot of those questions until I know what game I am making. For example I was wondering how the user would put spells a hotbar, but that depends on, among other things, how many spells there will be. I haven't even worked out the spell system yet (or even decided if I will have spells!)

So I have reached this conclusion: Design the game before making it

Until now I have been trying to make an enginey kind of sandbox and worry about what game I am making later. I know I am making a rogue-like but what is the setting? (medieval? sci-fi? fantasy?). Does it have magic? What is the skill system? What is the XP system? What items will there be? What monsters will there be, etc. How does it all fit together? That's the key part: fitting it together. If I just implement things separately. they won't tie together. I mean that's how minecraft was done and while it's one of the best games ever I think a general weakness of singleplayer is that there was no focused game, just cool bits and pieces being added on in each update. Eg wolves, how do they really fit into the game?

I don't expect to be able to design the game completely up front. There will be discovered problems and new ideas that will modify things, but even with a rough design it will be much easier to prioritize things, faster to develop and the game should be better at the end. I can also bounce the rough design off people who might turn round and say "no way that sounds boring!" and then I can go ahead and do it anyway in defiance. So next post will outline exactly what the game is, the setting, the ending, all of it.

How do other people do all this? Do you already have a 90% complete game design written down?
stuff2.png

The above mess is what I have so far. Please excuse the layout and the colors, it's all temporary. I am slicing so a lot of it is left unfinished.

  • Top Right: Equipment window. Works the same as the inventory and floor space windows except you can only drop the right item class into slots. I just realized I have forgotten a slot for a robe/cloak. I added 4 test items: A club, a dagger, a helmet and boots.
  • Middle Right: Player attributes window. Only has three attributes at the moment. Melee is the melee attack damage the player does. I broke this during performance optimizations mentioned later which is why despite the player boots and helmet it still reads 0 for the armor level and 0 for melee.
  • Lower Right: Floor space window just showing you what is on the floor. I guess this one will need a scroll bar as a floor tile can potentially hold infinite items (better solution?)
  • Lower Left: Message log. I have a static method which can be called from anywhere to add a new message to the log. Getting messages out is fine for now. Fixing the font, and the grammar is a job for much later.
  • Top Left: Inventory window. Shows what the player is carrying. The player can only carry a finite number of items.
  • Middle: Uh not much space left for the map is there? The resolution is 800x600 and I think that resolution should be supported. I am having trouble figuring out what the best position for the layout is to balance screen space with usability. It is possible to hide each window with a key.

    I added a new monster, a mummy, to test a creature that moves much slower than the player. It moves only one tile for every 5 tiles the player moves. I am glad I did this test as it uncovered an exploitable bug in the game. The player is able to jump towards the mummy, hit it, and jump back again before the mummy's turn. Repeated use of this technique means the mummy is unable to ever hit the player unless it can somehow corner them.

    You might say that's realistic - a faster player can kite the slower mummy. But in my opinion it renders slow creatures almost useless in rooms where the player can easily dodge round them. I think the mummy should move slower but have a similar attack speed to the player, ie it should be able to grab the player if they come too close. What I was thinking of doing to "fix" this was to allow monsters a chance to immediately counter-attack if they are attacked.


    Performance

    I started noticing some stuttering. Turns out I hadn't realized the C# garbage collector would pose a problem. I ran the .Net profiler against the program and discovered the game was creating megabytes of garbage strings and Vector2 objects every half minute. The garbage collector was having to clear that up, which took substantial time vs a frame, which was leading to frequent stuttering. The problem was that during each Draw() cycle I was creating various objects rather than reusing existing ones. I spent some time going through rewriting allocations until the profiler now looks a lot better. My biggest overhead now is creating DepthStencilState and RasterizerState objects every draw frame, I'll have to investigate if I can do that some other-way later, but for now the stuttering is fixed. I just need to bear in mind from now on to not allocate objects unnecessarily. But this is definitely a big deal for making a game in C#/XNA! Completely don't care about the garbage collector when I am making windows applications, but evidentially you have to care a lot to make games. If you ever know anyone starting off using XNA to make a game then warn them about this!

TODO list

TODO List/Essay

Message Log
The log that records the player's observations. Eg who bit who. After hectic turns the player can go back and review everything that happened. In the UI it will be a list with a scrollbar. It'll only store a certain number of events, or events for a certain number of turns. This TODO item is in progress.


Skills
This is more of a TOTHINK. I was planning on making all skills kind of powerful/useful to the player, not just attribute or combat modifiers. Here are five skills I was thinking about.

  • Hearing. This is an active skill that gives the player the ability to focus on hearing things. If they use the skill there will be a chance of detecting nearby things (that make noise) which are out of visual range. If something is heard then it will appear in the message log. Eg the message "you hear the soft padding of large feet to the North", or "you hear water to the east". Improved level of this skill might increase the chance of hearing things, the range, and make the information more specific.
  • Clairvoyance. Magical skill. Similar to hearing except it allows you to sense events much further away, even potentially on the other side of the world. This will be a passive skill however. It provides a chance of detecting certain events in the world and putting a message in the log. For example "you feel you are being stalked". With higher levels of the skill the chance could increase plus the information more specific, eg "you feel you are being stalked by a big creature", "you feel you are being stalked by a big creature to the north", "you sense a bear to the north is stalking you".
  • Possession. This would be an advanced magical skill. Allows you to temporarily switch control from your character to another creature. You can then control that creature as if it is you. You can shift back at any time. While doing this your own character is stationary and vulnerable to attack. If the creature dies under your control you shift back into your real character. If your character is attacked while you are possessing another creature you automatically shift back. There would probably be a range limit on how far you can walk the possessed creature away from you before you lose the link. Also probably a time limit. Although with an exceptional level of the skill it would be nice to control the creature permanently with unlimited range.
  • Empower. This isn't really so much a skill. It basically sacrifices your vitality for magical ability (perhaps mana). Increasing this will reduce attributes like health, strength, speed, etc in exchange for massively increasing magic ability. Therefore if you want to be a wizard type you can go partially down this route (I want to avoid fixed "classes"). Going fully down this route though will leave you largely immobilized (at which point the possession skill would come in very handy).
  • Bind. This allows you to bind some of your power and attributes into a wearable item of some kind. The downside is if you take it off you lose those attributes and power. The plus side is much better - if you die you will live on in the item with the attributes the item has. Anyone who wears the item will become possessed by you. After you die there is a dice roll. If you lose that roll the item is never worn (perhaps it's destroyed or thrown in some chasm) and you die - game over. If the role succeeds you are "reborn" as a creature unfortunate enough to have put the item on. You can even put your eggs in multiple baskets by splitting your powers across multiple items, increasing the chance that one of them will be worn and you will play on. Although in that case to regain your full powers you must then seek out and reclaim all the other items which may have by then been scattered through the world.


    Equipment screen - It'll be like the inventory screen but with slots in helmet, boots, gloves, etc positions. Need to make some test wearable equipment for this.

    Pathfinding - At some point I'll need A*. Should be fairly easy to implement but I need to allow calculations to be made over multiple frames to support really long paths, or just cheat.

    Random Map/World Generation - The game is going to be kind of sandboxy so the world is randomly generated. I am going to have a surface world which will need to have random towns and stuff. I'll probably look up how other people do it.

    Sound - not a priority. My headphones have broken anyway (that old one side doesn't work problem)

    Giant Multi-tile Snake - just for fun. I've always wanted to make a snake that trails 20 or so tiles. In the game it would be what I would call an "unfightable" class of creature you just don't want to meet. Ie you need to just run. If you even try to fight it in melee it will just swallow you. There might only be a handful of these in the world somewhere and you'd just have to be unlucky to encounter it. It won't be the worst class of creature though, I have another class planned I call "unsurvivable" (there are always ways though...)

    Shadow Weed - another for fun creature. It's a plant that feeds of darkness and spreads destroying everything in it's path. It's only barrier and it's weakness is light.

    Character Attributes - currently they only have health and speed

    Combat System - it'll be very simple. Not going for realism, just simple attributes and combat.

    More UI work - bah UI work is the most tedious.

    Lighting - proper lighting system to support "dynamic light" from placed torches, etc.

    Content - So far I have just been implementing things and moving on. Eg one monster, two types of tiles, three animations. Eventually I need to start adding more tile types, monsters, etc. Looks like there are months work left. Due to being familiar with my underestimate ability I would say there is a year work left at least (the above plus other undiscovered features).

    Quest - Another TOTHINK. What is the point of the game? The story? I thought about it a bit and decided the story of the game is you are being chased by a powerful group of mages. You escaped from them through a portal to another world, which you find yourself in now. You have limited time until they follow you. The ultimate point of the game is to build up your powers to the point you can face your pursuers down, but you won't have enough time to do that in the world you spawned in. Instead your sub-objective is to "find a way out" of the world itself. Either through building a portal, finding a portal or by some other means. When you exit the world you find yourself in a different randomly generated world. You can keep jumping worlds like that until you think you are ready at which point you can build up defenses (traps, monsters) etc and face them down (and if you fail you can of course duck into that portal you have ready).

    TODONT List

    XP - I am tempted not to have forward facing XP and leveling system. The player would develop their character through acquiring/improving skills and acquiring better weapons/armor and ultimately they would have to construct a defensive "lair" for the final showdown.
It's been over three weeks since the last entry where I wondered How To Implement Graphical Feedback in a roguelike. Thanks for the advice. I have been doing more thinking than coding. I am not happy with spending three weeks stuck on a problem, and I was questioning whether I was getting bogged down in a pointless obsession with having animation. Afterall most roguelikes, including famous ones, don't have animation and they play perfectly fine. In fact animation could easily reduce gameplay.

And that's one reason I have spent so long thinking about this. The other reason is that it turns out the animation solution chosen heavily influences the design of the turn system and the the way actions are performed. I didn't expect that, I was naively thinking animation was going to be some trivial visual thing, but no now I've looked into it I think it's possibly the most complicated part of the entire game. It's the only part of the game I can foresee that will be massively difficult and annoying to go back and change later, which is why I have been willing to spend three weeks to try and reduce the odds of that happening. I dread implementing some animation scheme and then in 2 months time finding a fatal flaw in it that requires a rewrite.

I have coded up a test implementation of the solution I reached that includes three test animations:

  • Movement animation - the creature slides to its new tile.
  • Melee animation - the attacker nudges towards and back again from the target.
  • Damage animation - a number rises above the damaged creature indicating how much damage was done.

    Apologies for the poor video quality (the game graphics are not much better tho!) - plus there's no sound.

    [media]
    [/media]

    Some details:

    • Animations run sequentially. The cycle is Turn, Animate, Turn, Animate, and so on. I did consider parallel animations but there are huge problems with that. I'll probably write a post about it at some point.
    • The animation speed can be changed.
    • The player doesn't have to wait for all the monster animations to complete. Action keystrokes are queued. If there are keys in the queue then the animations run at max speed. In this way the response to user key presses is instant and animations take lower priority.
    • The damage animation is shown in real-time even if you skip. This is so the user gets a warning that they were hit even if they get over-excited with the key tapping.
    • Possibly most important: Animation can be disabled.

      It works well enough for me so far. There are minor downsides, it's made the code more complicated and less "pure" for example. I need to do more testing with more complicated chains of animations to make sure there aren't any annoying gameplay issues. I'll post about more implementation details once I've confirmed this works with more testing. I also need to record here all the solutions I looked at and the dead-ends I found, before I forget them.

      I'll still be implementing a message log at some point. The animations only go so far.
tap-tap-tap-taptap-tap-tap-tapHere's a partial screenshot to help explain things:

shot1z.png

First a quick description of the image: You can just about make out the tiles in the wide open floorspace. The gray blob in the middle is the stand-in icon for the player's character. The two monsters nearby are zombies but I know they look more like green men with bandages on their heads.

The multiple blue and red items on the floor are test items and serve no purpose. The grid at the lower right is the floor view screen which displays the items on the tile at the player's feet. For the sake of this post it has no relevance.

Quick explanation of game-play: The player makes a move using the WASD keys then the zombies get a turn to move. Then it's the players move again, and so on. This all happens fairly instantly as you'd expect. No sooner as you've hit the W key the zombies will move too and it's your turn again. This quickness is important and players will expect it. No-one wants to have to wait half a second per tile moving down a long empty corridor. You want tap-tap-tap-tap to work or even holding the key down.

Problem Background: For this kind of movement there is sufficient graphical feedback - you can see the player and monsters move. But what about combat?

The vast majority of rougelike games provide feedback in the form of a message log. So after you make your turn to attack the zombie the following events might appear on the log telling you what happens:
-You miss the zombie
-The zombie bites you

When combat is hectic you can get loads of messages coming out telling you what each monster in range has done. The message log is also used outside combat to provide other feedback:

-You can hear water nearby

It is also used to provide return state for various actions. Eg you could examine a monster on a tile and the message log can provide a detailed description:

-You see a troll. It is wearing leather armor and carrying a hammer and looking very obvious.

It can even provide feedback about UI actions:

-You can't remove the ring. It is cursed.

Also of course it can be used for conversations with NPCs. It can be used for almost all feedback. The other two benefits of a message log are:

  • The player can ignore the log entirely if they want. Feedback in the form of messages does not slow the player down.
  • The log keeps a history of past turns if the player wants to go back and review something they missed.

    I will probably have a message log but...

    Problem: I want graphical feedback too. It's a graphical game after-all. Perhaps not all actions will have graphical feedback, but I would like it at least for common actions like melee combat. Also it would be nice to do some cool effects for magic and the ability to show the path of projectiles like arrows would be useful.

    What kind of graphical feedback do I mean? I don't mean smooth animations of the player swinging their weapon. It's a tile based game and I am not good enough to make good animations. I am thinking an outline round the attacker with the target flashing would be sufficient. Perhaps with little damage numbers rising and fading. Sound could also be used to feedback the impact severity (miss, deflected, or hit). Perhaps the target could flash white if the attacker misses and red if they hit. Perhaps blue if they hit but the strike was repelled by armor. I don't know the specifics yet, the point is just to add this kind of feedback.

    The problem is that if the action happens instantly the player won't see the feedback.

    Complications:

    My game is currently single threaded. Player/Creature turns occur separately (ie not all in one game frame) so that I can already add a pause after each one. But within a single turn itself I am currently in a single frame. I cannot perform an animation mid-way through a turn and then continue the turn.

    For why I might want to do this take the following extreme example:

    1. The player fires an arrow at an exploding barrel
    2. The arrow hits and the barrel explodes
    3. The explosion damages a wall
    4. The wall falls down and hits a zombie
    5. The zombie dies

    This all happens in a single turn, a single game frame. On the next game frame the zombie has the state of "dead" and is drawn dead, the barrels no longer exist and are not drawn. Of course I could have all the above events in the message log so the player could see what has happened, but not as nice as a graphical feedback for each one is it?

    Preferably the following should happen for the turn:

    1. Arrow sound.
    2. An arrow projectile is created and moves from the player to the barrel.
    3. An explosion sound.
    4. Barrel image changes from intact to destroyed. Screen flashes, fire projectiles are emitted.
    5. Wall collapse sound. The wall image changes to collapsed.
    6. The zombie makes "ARRRHHH!" sound and goes from living image to dead image.

    Much more fun. But each of these effects requires time to display it. The complexity of the chain of events means I can't just process the turn and then perform everything that happens. For one thing my object model is directly altered by the actions so like I said if I process all the events and proceed to the next game frame the zombie will appear dead and the barrels will be drawn destroyed immediately after.

    I can't see any other way but to perform the animations as each action unfolds, eg interleaving the actions with the animations. Only performing animations after the actions:

    1. The player fires an arrow at an exploding barrel
    2. An arrow projectile is created and moves from the player to the barrel.
    3. Calculate whether the arrow hits. It does. Unload damage onto the barrel.
    4. The barrel "dies" and triggers an explosion.
    5. An explosion sound is emitted. Barrel image changes from intact to destroyed. Screen flashes, fire projectiles are emitted.
    6. Splash damage from the explosion is calculated. Damage is unloaded on a nearby wall.
    7. The wall "dies" and triggers a collapse animation and sound.
    8. Splash damage from the wall collapse is calculated. Damage is unloaded on a nearby zombie.
    9. The zombie dies and triggers a death animation and sound.

    The problem is all the actions occur beneath one call to game.Update(), which is one game frame. Eg in step 5 I can't freeze the code inside barrel.Explode() and then return to it after an animation has happened to calculate splash damage.

    Another complexity is that the user must be able to skip all animation if they hit a movement key. Remember they should be able to tap-tap-tap the keys. if they miss stuff doing that it's their own fault. But you really don't want to have situations which I have experienced in so many turn based games where there are 50 ranged units on the screen and each turn you have to sit through a minute of animation as each of them fires with no way to skip it.

    I can vaguely envision a solution here involving threading, but any ideas? Perhaps I have missed something obvious. Perhaps I have even screwed up the design to find myself in this situation?

    On a side note I have a very rare week coming up in which I will not have access to a computer of any kind, so only thinking progress will be made and if anyone does reply I might not be able to read it/reply for some time, it isn't because I am ignoring it.

progress update

Since the last update:

  1. Implemented inventory system.
  2. Implemented basic UI for the inventory system.
  3. Played some Castle of the Winds (http://lkbm.ecritter...w/download.html)
  4. Played some Dwarf Fortress (http://www.bay12games.com/dwarves/)

Inventory System
The inventory system doesn't just cover the player's inventory, but also inventories of monsters, the contents of containers like chests, the floor space of tiles and even (eventually) the player's worn equipment. I figure that all these are containers in which items can be placed into a specific (or any free) slot. By implementing a common system for all of these it means one item transfer system can be made that works for all of them and the UI can bind to any possible item container to display/interact with it. I made the following gameplay decisions with the inventory:

One item per slot, One slot per item
In some games bigger items take up more slots in the inventory. Stalker (or should that be S.T.A.L.K.E.R?) springs to mind where the rifles would take up huge amounts of slots in the backpack and the ammo would take up just one slot. I wanted to avoid that to keep it simple. I don't want any of the hassle of packing algorithms and I never find packing luggage that fun. So it's one item per slot. On the downside it does means a shield will take up as much space in the inventory as a spoon...

Inventories are space restricted, not weight restricted.
Another simplification. I did at least start off trying to implement weight restriction, but due to a catastrophic experiment involving nested containers, rings of strength and bags of holding I ditched the idea for making inventories limited to a certain number of slots instead. Tracking weight stats is kind of boring anyway - how much can I carry? How much am I carrying? how much does that shield weigh? Slot restrictions are much easier to visualize. I can tell how many slots I have left at a glance.

Items can be stacked
I didn't want this but I am forced down this route once I am slot restricted. The first items I made for testing were blue gemstones and red gemstones. They are small things the player can pick up and it was clear straight away that picking up 10 of them took up a ridiculous number of slots (10!). I want the entire inventory to fit on one screen really. To do that I need stacking for small items at least...

The UI
Currently there is a player Inventory screen which can be displayed and hidden pressing the 'I' key (wow!) and a floor space view (which is useful considering you can't see what's on the floor behind the player sometimes). Items can be dragged between the views and stacked, etc. I need keyboard support for the inventory eventually I guess but for now it is entirely mouse driven.

Inventory Implementation
The following text is even more boring than the text above.

The basic class for inventory is ItemContainer. It's a container of items. Really it's a dictionary of items, mapping slot indexes to specific items. The player's inventory and the tile's floor space are both ItemContainers. Even the cursor has an ItemContainer, with one slot, so that it can "carry" items in drag/drop operations.

The most important method of the ItemContainer class is AddItem(Item). That does slightly more than it suggests. It not only adds an item to the container, it first tries to remove the item from it's existing container. I say try because the action can fail. Both containers and the item itself get a say as to whether the Add/Remove operation succeeds. I am thinking ahead to eg an item refusing to be removed from worn equipment if it's cursed. If AddItem fails a reason is returned, which eventually will be put out to the UI.

UI Implementation
An InventoryWindow containing many InventorySlotWindows can be bound to an ItemContainer to display the ItemContainer's contents. When an InventorySlotWindow receives a MouseDown event it handles the dropping of an item into the underlying ItemContainer slot, or the picking up of an item from that slot. To pick up an item it simply calls the CursorContainer.AddItem(Item) and now the cursor has the item. When the cursor is drawn if it's ItemCollection contains anything the icon for that item is drawn beneath the cursor.

Stacking Implementation
I now have an Item class that derives from Entity. Items are things that can be carried. The Item class has a StackCount property for how many items are in the stack and a StackLimit property. Items that cannot be stacked have a StackLimit of 1.

Things Left To Do:

The ever growing list. I am not even really working on the actual game yet, it's all foundational stuff so far. I spent so long on the UI system because I figure I can use it in other games too.

  • Inventory system. Mostly done but a little work left.
  • Inventory/Equipment/Floorspace UI. Need to implement equipment UI and improve inventory.
  • Message/Log/Event Window Need a UI to display messages to the user. Errors, game events, etc
  • What is the Point? can't really make a HUD or player stats display or a lot of other stuff without knowing how the game will work - eg what stats are there? what IS THE GAME?
  • Action "Animations" adding visual feedback. At the moment turns are instant. You don't "see" what happened. Need to slow turns down so you can see arrows flying or fireballs exploding.
  • Sound?
  • Random Map Generation
  • Saving/Loading - probably need a game first!
What is an inventory?
It's kind of a container the player has to hold Items I guess. Seems simple enough. Coding this should be real quick.

What about creatures can they carry items?
Oh..yeah of course, so an inventory is not player specific after-all, inventories can be owned by any a creature - including the player.

What about a chest and other containers in the map?
Didn't think of that...I guess those are furniture. For simplicity I can just make them a creature that cannot think or act I suppose...

What about a bag?
...a bag?

Yes a bag. A container the player can carry
Oh. *facepalm*. I didn't think of that either. A bag would be an item but it also has an inventory....

Can the player carry a bag in a bag in a bag?
I guess....there's probably only going to be a weight limit.

How are you going to handle the UI for nested inventories?
...

And what about corpses? They have inventories right?
Yes they still have inventories the player can browse

But you can carry corpses right?
wow it gets even more complicated. Can you carry a dead creature while it holds all it's inventory? That means you aren't just carrying items you can also carry creatures. Hmm maybe dead creatures just drop all their items to the floor. Would make it easier...but has downsides too.

What about worn equipment like armor though? Does that just fall off onto the floor?
Uh I guess it could...unrealistic but that would also make things easier.

Now, weight restrictions...
[conversation continues into the night. No coding is done]

Zoom + Combat


  • Implemented dumb AI for zombie
  • Implemented "combat"
  • Added zoom ability

    [media]
    [/media]

    map is probably a bit too dark I should light it up a bit.

    Zombie AI

    The zombies move towards the player if they can see the player. If the player goes out of view they move towards the tile they last saw the player on. After 20 turns of not seeing the player they "forget" about the player and revert to random walking. Zombie brain code below. I am hoping I can keep the entity AI code fairly concise and highlevel with the bulk of work being deferred to lower level methods, such as Entity::MoveTowards(Tile), Entity::IsVisible(Entity) I have used below.


    Tile lastSighting=null;
    int memory = 0;
    //called when it's the zombies turn
    public override double Update()
    {
    //if can see the player move towards player
    if (IsVisible(RpgGame.Player))
    {
    //remember this sighting of the player
    lastSighting = RpgGame.Player.Tile;
    memory = 20; //fresh memory of seeing the player
    //move towards the player. This becomes an attack if the zombie attempts to move into the player's tile
    return MoveTowards(RpgGame.Player.Tile);
    }
    //zombie cannot see the player
    //if the zombie can remember where it last saw the player move towards that location and wait there
    if (memory > 0)
    {
    memory--; //zombies are forgetful
    return MoveTowards(lastSighting);
    }
    //zombie cannot see the player and cannot remember ever seeing the player
    //default behavior is to move about in random direction
    return Move(Map.GenerateRandomCompassPoint());
    }


    One TODO above is that I have the player set as static so all the zombies can look for the player. Really though the zombies and all other creatures should scan the tiles around them and spot the player (and anything else) rather than having it hard-coded like this.

    Also the MoveTowards(Tile) method happens to be flawed and needs fixing as zombies easily get stuck on walls.

    AI should probably be handled by a separate class so that similar behavior can be shared by different creatures. I imagine a lot of creatures will have a brain like a zombie.

    Combat

    It's not really combat, entities start with health, if an entity moves into a hostile entity it does damage to that entity (so the zombie AI which moves towards the player covers this). When an entities health reaches zero it dies. Dead entities de-register from the timeline (they aren't given anymore turns) and become part of the tile's floor items rather than being the tile's occupant. This allows other creatures, including the player, to occupy the same tile as a dead zombie. Floor items are drawn behind the tile occupant. Big flaw at the moment is you can't see damage being done, or even see that the zombies are hitting the player.

    Zoom ability


    So far the camera has been fixed 10 units away from the screen, the FOV is 45 degrees and the resolution is 800x480 (yes that's a bit weird I should correct that - at the moment it's running in windowed mode not full screen). This meant the screen could only fit an approximately 15x10 tile area. That's a bit restrictive. Now that I am being chased by zombies it's useful to see a larger field. So I added the ability to pull the camera backwards and forwards. It's a bit jumpy because it moves it back and forth in discrete units. Ultimately it might be better to have different zoom levels, eg near, medium and far where far would be a kind of distant "map view" that isn't really playable.

    I immediately discovered that when I zoomed out the map was still only being drawn as a 15x9 tile area and there was a large gap at the edge of the screen where nothing was being drawn. Idiot, I forgot I had hard-coded the 15x9 area. Now I had to calculate the amount of tiles that need to be drawn on the screen at different zoom levels. If I need to draw a 15x9 tile area when the camera is 10 units away from the screen, how many do I need to draw when it is 15 units from the screen?


    I could trial and error and hard code more values, but then I thought what if I change the screen resolution or want to change the FOV? I figured I needed calculate how many tiles are on the screen from the screen resolution and FOV and camera distance.


    So take this example. 10 units away from the screen with a 45 degree FOV is a triangle like this.
    trianglesf.png
    After relearning trigonometry yet again (why can't I just remember that stuff?) I worked out that half of 'w' is the tangent of 22.5 degrees multiplied by 10.


    So w here is 8.28. Because a tile on the map is a unit squared this suggested to me at 10 distance the map needed to be drawn as a 8.28 x 8.28 tile area to fit the screen. Well round it up to 9x9. That matches what I found necessary for the height part of the map, but not for the width part. 9 tiles is woefully short of the 15 tiles I found necessary to keep the screen filled.


    It's probably because the screen width is larger than it's height. The resolution is 800x480 right? So I spent a good hour guessing and cursing at how any of my attempts to fit a 800x480 grid into the calculation didn't fix things. I would have read a manual but it's one of these problems where I am not sure what to search for short of taking an entire week reading everything.


    Then I just happened to be looking at the GraphicsDevice.Viewport in intellisense and noticed the property AspectRatio set to 1.66666. This is because 800 divided by 480 is 1.66666...


    So it was obvious. 8.28 times 1.67 = 13.8, which rounding up matches the 14 tiles I found necessary to fill the screen. So I guess the height, being less than the width doesn't have any ratio applied but the width does....

    Then I thought, wow I better write this all down so I don't forget in future. So I opened notepad and began writing a note wondering whereI could put the note so I can find it again. If only I had a central place somewhere where I could write stuff like this down so I can go back and review it in future...some kind of journal...that's idiot x 2 today.

    Things To Do

    Partial list of large pieces of work that are on my mind that need doing. Doesn't include an abundance of stuff I am probably oblivious to.

    • Inventory system. The player and other creatures need to be able to carry stuff, pick stuff up, drop it. Supposedly there are weight restrictions or space restrictions. Then there is wearable stuff, eg armor, which is kind of like a slot-based inventory.
    • HUD. Displaying player stats (health, etc), inventory browser, equipment browser (stuff the player is wearing). Allowing things to be moved between inventory and what the player is wearing. When picking up items from a chest you need an inventory screen displayed for the chest, but also the player's inventory so that things can be transferred. Do you also show the player's equipment screen so they can put stuff on? Screen space will be an issue and messing it up will detract from gameplay.
    • Action feedback. Adding combat highlighted that some kind of feedback is needed. At the moment you can't tell if the player gets hit by an enemy. Their turns are instant and silent. There could be a text log saying "the zombie bites you", but perhaps there needs to be some kind of "animation" like the player's image flashing red. That would require turns to last a little longer in order to display the transition. Also when I set the zombies to move 3 times faster than the player so that they move 3 tiles every time the player moves 1, it looks like they are jumping. There should be a smooth transition so you can see the path they take. Again that requires some kind of delay during the zombie's move so you can see them moving.
    • Some kind of efficient field of vision algorithm for creature AI so they can spot hostiles or other interesting things that come into their field of view. I guess I might as well replace the player's field of view algorithm too.

Zombies

What I have done is:

  • Added mouse input/tile selection
  • Added player lighting
  • Added the turn system
  • Added zombies
  • Integrated the zombie AI and player controls into the turn system

    [media]
    [/media]

    Mouse Input

    Trace a ray into the map plane and get the X and Z coordinates of the collision.

    Player Lighting

    It's not really lighting. It's just a cheap trick, I just fade off the brightness the further a tile is from the player. Makes it more atmospheric though.

    Zombies

    The zombies move slower than the player. They cannot currently attack (there is no combat) and they just move in a random direction during their turn at the moment. They are completely oblivious to the player. They are blocked by walls but at the moment they can walk through each other and the player. Below is the source code for the zombie class.



    class Zombie : Entity
    {
    public Zombie()
    {
    _moveTurnUnits = 0.5; //length of game time it takes a zombie to move one tile
    }

    protected override Texture2D CurrentTexture
    {
    get
    {
    return _map.Game.Content.Load("zombie");
    }
    }

    public override double Update()
    {
    return Move(Map.GenerateRandomCompassPoint());
    }
    }



    Time and Turn System

    This is what the bulk of work has gone into. I kept redoing it, even once deleting the whole thing and starting again.

    This is what I was after:

    • At the start of the player's turn the game pauses waiting for the player to input the action they will take.
    • Possible actions include moving to a neighboring tile, picking an item off the floor, throwing something, etc.
    • The player can only perform one action per turn.
    • The length of the turn in "game time" is determined by the action the player takes.
    • Once the player has acted it is the turn of each creature on the map to act. They get as long in "game time" as the player took during their turn.
    • A creature might be able to perform multiple actions during their turn. Eg if the player took a lengthy action of reading a book a creature might have time to take several movement actions.
    • Creature turn must be fairly instant. There can't be much of a delay, perhaps 200ms at most. It should be possible for the player to hold that cursor key down and move quite fast.

      A complication of this is that creatures can move at different speeds. Take the example of a Tortoise. The Tortoise is 10 times slower than the player. During the players turn, the player presses W and so the player moves North by one tile. It's now the tortoises turn. The tortoise chooses to move North too...but it's 10 times slower than the player so it should only move 0.1 tiles. But all creatures must be on discrete tiles, they can't be partially in one tile and partially on another.

      What I settled on was to actually use a timeline of events. There is a game time. It's single number that starts from zero and increases as the game progresses. Events are scheduled to occur at given times. Each creature schedules their turn as an event on the timeline. When time reaches that event the creature performs their turn. The event is then reinserted into the future by the amount of time it took the creature to perform their action.

      The events on the timeline are sorted by time, so that the first event on the timeline is the earliest.

      1. Advance the game time to the earliest event in the list
      2. Remove the earliest event from the list
      3. Process that event
      4. Go to 1

      When each creature is added to the map they insert an event into the timeline. This is effectively a callback for their turn. When the event is pulled the creature is notified and performs their action. The creature returns how long the action took. The event is then reinserted onto the timeline with that delay from the current time. This allows different speeds for different creatures and different speeds for different actions. The timeline should also allow other things to be scheduled in the game. Eg timed actions, fuses, etc.

Line of Sight

This is what I have now. The player can only see tiles that are in their line of sight. Tiles that are outside their line of sight are drawn pitch black.

shadowuh.jpg

Rather than just explain where I ended up I'll explain the steps I took to get here.

Motivation

The player should not be able to see through walls. Why? I was going to say because it's unrealistic, but then I realized this is a 2D grid based RPG. It's unrealistic anyway, and if I shunned anything that was unrealistic there could be no magic or monsters in the game.

So perhaps the word is "unbelievable". Magic and monsters are unrealistic, but in the setting of a different world they can be believed. The world needs to be believed. As soon as the player thinks "that makes no sense" you've started losing them. A 2D grid and turn based game is on thin ice as it is in terms of immersion, if the player starts questioning the logic of the game world it all starts unraveling.

The player, being human, is familiar with how a human views a world. Therefore they expect by default that solid objects obscure things behind them. So on those grounds alone I want to make sure the player cannot see through walls. I could possibly come up with a game world based excuse such as the character has x-ray vision, but I don't think a world that is made of obviously contrived excuses can be believed.

Another reason for not allowing the player to see through walls is that I think discovery and the unknown are key parts of an RPG.

First attempt

At first I underestimated the complexity of the problem. I thought "hey this is pretty simple, all I have to do is trace a line from the middle of the player's tile to the middle of each distant tile and see if it collides with a solid tile on the way". Here is what I was thinking:

naive1.png
Testing whether the tile marked A is visible to the player by tracing a line from the player to tile A. All the tiles that are intersected by the line are tested. Because the line passes through the brown wall tile the test fails and tile A is considered not visible to the player.

Fortunately I did not implement this simplistic algorithm but went to google and looked up line of sight algorithms for nethack like games.

I came across this. I would usually dismiss stuff like this and keep searching but I noticed it was written in September 1989! Ancient wisdom!
http://www.fadden.co...c/fast-los.html

I didn't understand the proposed algorithm and it's probably not wise to use an algorithm over 20 years old without checking for newer improved ones anyway. But it did highlight some key problems I hadn't considered.

Take the following situation:
naive2.png
Player against a wall. Lines are traced from the player to each tile of the wall. Green lines are lines which go from the player to the target tile without being obstructed by another solid tile. Red lines are obstructed by other blocks on the wall itself

The player is up against a long straight wall in the example above. Now if you are up against such a wall in real life and you look to your left and right, you should be able to see the full extent of the wall. However the naive algorithm I thought of only allows the player to see the 3 nearest tiles of the wall.

naive2b.png
How the naive algorithm would draw the wall. Only three tiles are drawn and the player does not know if the tiles in darkness are wall tiles. This is contrary to expected behavior. The player should be able to see the whole extent of the wall from where they are standing

Back to the believability of the game: The above behavior is less believable than I am willing to tolerate. The player will expect to be able to see the full extent of such a wall.

Fixing the problem

To solve the wall problem I devised an extra test for the naive algorithm. An additional trace is performed if the trace to a tile's center fails. This second trace is to the tile's edge.

naive3b.png
If a trace line to the center of the target tile fails, a trace is attempted to the middle of the tile's edge. If that succeeds and the tile is solid then the tile is considered visible

Now all parts of the wall are visible. Hurray. There is a question remaining though about what happens if the "edge" case tile isn't solid as in the following example:
naive4.png
The center of tile A isn't visible to the player, but the edge is. Tile A is a non-solid. What should happen?

In terms of believability the answer to this question is not obvious. There are a number of options that are all believable enough:

1) Tile A is obscured from view (current behavior)

2) Tile A is shown in full with all it's contents

3) Tile A is shown as texture only, with a "fog of war" effect. Contents are not shown. This is to simulate that the tile is only partially visible allowing monsters, etc to effectively be hiding behind the wall.

It comes down to a choice. For now I stick with #1, but I want to eventually move to #3. Mainly because #1 is slightly flawed. An observant player knows the obscured tile is empty because if it wasn't it would be drawn solid. They can see part of the tile so they should be shown if the floor is made of stone, wood, etc. But I think it better that they can't see the contents (items, monsters).

Another problem: symmetry

naive5.png
Obscured regions are asymmetric. Because the diagonal lines are theoretically perfectly hitting the corners it's questionable whether they graze the tile or miss it. Due to precision error this manifests in an artifact.

naive5b.png
Solution is to "shrink" solid area of tiles so there is a slight gap around the tiles. The traced diagonal lines now consistently miss the tile and produce no artifacts here.

This doesn't of course solve the precision error. There will still be a precision and symmetry issue, but now it will only occur where the trace line grazes the shrunken tile. The artifacts no longer occur in the very common and obvious case of pure diagonal trace lines. The artifacts are pushed back to happening in less obvious scenarios which the player is less likely to notice. That's good enough for me.

It does though allow the player to see along diagonals:
naive7.png
Player can see through the diagonal space between the two wall tiles

This is perhaps an advantage. A lot of roguelike games support diagonal movement and sight. I don't know whether I will. Ultimately if I don't want the player to be able to see through such gaps I could just enforce the game map so that solid blocks separated by only a diagonal aren't allowed

Flaws

The technique I use is to trace lines from the player to every tile in turn that needs to be drawn to determine if they are visible. There are better algorithms out there both in terms of performance and reducing artifacts:
http://roguebasin.roguelikedevelopment.org/index.php/Field_of_Vision

Additionally I need to consider that the line of sight and field of vision algorithm will not just be used to determine what the player can see but will be used more generally for AI purposes - ie what can the monsters see? It could also be used for lighting (ie which tiles are struck by the light from a torch). Both of these cases would increase the number of times the algorithm needed to be run and would probably require a better performing algorithm.

For now I am sticking with this simple solution, as it works kind of and I need to move on to other parts of the game. I can always come back and optimize/change this later.

Details

I have added two methods to the Map class.


public class Map
{
/// Returns whether a tile on the map is visible from another tile
public bool IsTileVisibleFrom(int tileStartX, int tileStartZ, int tileEndX, int tileEndZ);
/// Performs a line of sight test on the map
bool LineOfSightTest(int tileStartX, int tileStartZ, int tileEndX, int tileEndZ, TraceEndpointType endPointType);

enum TraceEndpointType
{
TileMiddle,
TileFarEdge,
}
}


The LineOfSightTest() method is used by the IsTileVisibleFrom() method. The IsTileVisibleFrom code is below:


public bool IsTileVisibleFrom(int tileStartX, int tileStartZ, int tileEndX, int tileEndZ)
{
if (tileStartX == tileEndX && tileStartZ == tileEndZ)
return true; //tile is visible from itself!

//calculate the x difference and z difference
float xDiff = tileEndX - tileStartX;
float zDiff = tileEndZ - tileStartZ;

//If the center of the end tile is visible from the center of the start tile then the tile is visible
if (LineOfSightTest(tileStartX, tileStartZ, tileEndX, tileEndZ, TraceEndpointType.TileMiddle))
return true;

//the center of the end tile is NOT visible from the center of the start tile.
//If the end tile is an empty space (ie floor) then it is not visible
Tile endTile = GetTile(tileEndX, tileEndZ);
if (endTile.Type == TileType.StoneFloor)
return false;

//The end tile is solid. There is one more check to make. If the edge of the tile is visible
//then the tile is visible.
if (LineOfSightTest(tileStartX, tileStartZ, tileEndX, tileEndZ, TraceEndpointType.TileFarEdge))
return true;
return false;


I won't post the LineOfSightTest() method code. It's nasty, mainly because it solves for one quadrant and for the other quadrants I swap or negate X and Z axes. Pretty common trick but it makes it a nightmare to read what's going on. This is what it does though:

naive6.png
Tracing a line from the player to the center of tile A. The entry and exit points of the line through each column of the grid are calculated (the red dots) and used to determine which tiles the line passes through and in which order

Initial Results

This is what I have so far. Visually it's horrific but I don't see any need to find/make quality textures at this point. I would waste time doing that. In my opinion the graphics shouldn't be better than the gameplay and currently the gameplay is at zero.

rpg2.jpg

The brown tiles are walls by the way, not mud pits or waffles. The "player" (that gray blob) can be moved around using the WSAD keys (to be clear there is no animation and the player image simply moves from one tile to the other instantly). The camera can pan using the cursor keys. The player cannot walk through the walls. That's it.

I should make it clear that I started this BEFORE the first journal entry so don't imagine I've done all this in 24 hours from scratch (although an expert would no doubt be able to do just that and more). I spent an age figuring out the basics of the high level shader language (hlsl) thingy and how to draw transparent overlays, how to tie that in with effects files in XNA and how to map textures.

World Representation

Here's the bare bones of the internal structure of the game world:


public class Map
{
private Tile[,] _tiles;

public Map(int width, int height);
public Tile GetTile(int x, int z);
public int Width;
public int Height;
}


public class Tile
{
public Tile(Map map, int x, int z);
public TileType Type;
}

public enum TileType
{
Wall,
StoneFloor
}



I went down the obvious route of the map internally being represented as a 2D array. I have a Tile class to represent a tile. Ultimately for extensibility I think each tile type should subclass the Tile class, but for now I use a TileType enum.

Rendering Implementation

The map looks 2D but is rendered in 3D. The world plane sits at Y=0 and the camera looks down from Y=10. I wanted to use 3D and shaders rather than 2D with blitting and sprites because part of the point of this project for me is to learn 3D and shaders in XNA.

I started off with a default XNA windows application project that draws a shaded triangle and corrupted it beyond recognition. The code in the Game class is now really a mess as it's full of the remnants of trial and error. It's simplistic to say the least. The Draw() method just pulls the tiles from the map one by one through the map::GetTile(x,y) method and renders them. Repeated calls to:

GraphicsDevice.DrawUserPrimitives(PrimitiveType.TriangleStrip, vertices, 0, 2, VertexPositionTexture.VertexDeclaration);

I know indexes and suchlike are probably the way to go performance-wise but I am going to stick with this for a while. I want to largely avoid spending time on optimizations for now, although I did optimize the draw code a little so that only tiles that are visible (or near enough) are obtained and rendered, not the whole map.

I am mulling over the idea of eventually having a massive, potentially infinite, game world that is loaded and saved to disk as needed.

Camera

The camera position is a Vector3 with the Y position is fixed (although later it could be controlled to support zooming) and the X and Z components controlled by the cursor keys. The X and Z camera values determine the middle tile on the screen (the camera is directly above it). I calculate the center tile during the Draw() method by:

int centerTileX = (int)Math.Floor(cameraPos.X);
int centerTileZ = (int)Math.Floor(cameraPos.Z);


And then I basically draw a load of tiles around that center tile. Enough that it fills up the screen.

Here's a diagram of the map and camera setup:
camerae.png

What this diagram tells us is that the artwork for this game is going to be terrible. It also shows how the camera sits above the map looking down and only the fraction (in red) of the map in the current view is rendered. As the camera moves across the map the red area will change. Because the map is fixed and the camera moves you can scroll fractions of a unit.

Entities, the Player and movement

My favorite part of this game design process is writing the gameplay classes. The rendering stuff I find is tiresome work in contrast. I don't know if other people find the opposite. I remember looking at the quake2 source code and seeing Carmacks class structure for everything that got me interested in how nice game engines can be. It's almost pure textbook OO and I don't get to do that or see that in many other applications.

I have an Entity class that will be a base class for all monsters, creatures, locatable monsters, creatures and probably items on the map. I think that's pretty standard for a lot of games. My entity class currently looks like this:


public class Entity
{
public Entity(Map map, int xPos, int zPos);
public int X;
public int Y;
public bool Move(CompassDirection direction);
//returns true if the entity can travel through the specified tile, false if it cannot
public bool CanTravelThrough(Tile tile);
}

public enum CompassDirection
{
North,
East,
South,
West
}


The base Entity::CanTravelThrough method implementation simply returns true if the tile has a type of TileType.StoneFloor and false if the tile has a type of TileType.Wall. This isn't the way I want to do it as it requires each entity type to list all the tile types it can travel through, when really you could generalize and say most entities cannot walk through solid tile types. I'll re-organize this eventually.

I have a Player class that is derived from Entity (it doesn't implement anything new) and the WASD keys are bound like so:

void KeyPressCallback(Keys key)
{
switch (key)
{
case Keys.W:
player.Move(CompassDirection.North);
break;
case Keys.A:
player.Move(CompassDirection.West);
break;
case Keys.S:
player.Move(CompassDirection.South);
break;
case Keys.D:
player.Move(CompassDirection.East);
break;
}
}


I render the player after the tiles are drawn using a shader technique that has a pixel shader that sets alpha to 0 for "pink/purplish" pixels, making them transparent. So all the entity images in this game will use pink to denote transparency.

I should probably take a look at some existing rouge-like code to get a perspective on how it's done but I am lazy. I'll get round to that eventually.

The next entry will be about implementing Line of Sight so that only the tiles that are visible to the player are drawn.

The Plan

Introduction

This journal is to document my attempt to make a game.

I have never made a game before. I have dabbled with things like opengl, directx and XNA in the past but never completed anything substantial. In fact I don't think I've ever finished a software project. I figure if I keep this online journal, maybe it will provide the necessary pressure during those low motivation periods to keep going.

My motivation for making a game is to get better at it. My theory is to start small with something that will challenge me at my current ability level without being impossible.

The game I am planning on making is a Nethack style game - a graphical tile-based RPG. The view will be down from above so it will look 2D. Fundamentally you have an inventory and you can go off exploring and looting some dungeon and surviving by killing monsters and leveling up. I have some ideas that will make the gameplay a little different, but initially I want to keep it simple.

That's the most important rule: keep it simple. So it will be single-player only, avoiding networking. I am going to try and build it "agile", getting everything implemented at a very basic and boring level first so that there will be a "game" very quickly, and then add the details later. Eg don't waste five weeks making dozens of super cool monsters with powerful AI. Instead spend a day making a zombie with AI that's dead simple, then move on to maybe adding simple sound to the game and then adding a simple inventory UI. Five weeks later you have a broad but basic game, rather than just a map filled with 51 varieties of monsters.

In the past I have used c++ and opengl, but for this project I will be using C#/XNA because I find development in C# a lot faster.
  • Advertisement