A Whole New World, Every Single Time

I'd thinking about how to implement a procedurally-generated overworld. Not yet looking at individual organic-looking tile placement, god no, but instead on how to organize a random world into an interesting underlying framework.

On the topic of things being interesting, my original plan was to make an overworld of wide open areas without changing the scale from dungeons or towns, with no way to travel on a world map (see Secret of Mana). Then I realized how terribly tedious and monotonous and repetitive and dull and uninteresting and dreadful and repetitive that would be, and thought instead of having a fast-travel option. I went back and forth between a Dwarf Fortress-style zoomed-out representation to travel quickly or a Diablo2-style waypoint option and select from a list of towns you've visited. It was the former which made me realize that, given the option, most (sane) players would choose the faster zoomed-out traversal, defeating the point of trying to catch their attention with repetitively repetitive repetition in the larger representation. It would also be tricker to randomly generate convincingly, and much more painful to try and save. So I decided to go with just the zoomed-out representation, because it's easier for me and less repetitive for you. Oh don't look at me like that. If this style of overworld is good enough for Final Fantasy, Chrono Trigger, and ADOM, it's more than good enough for me. More importantly, I doubt anyone would honestly want an alternative. Realism is only worth pursuing in videogames if it enhances the experience, and in this case it adds drudgery and repetition, not fun (a premise I'll cover further in an upcoming entry).

Okay I'm a Liar

Okay, so on reflection, I may have made a few misstatements last time.

Firstofall, the games is probably around v0.0.7 now; I forgot about making a menu system to initialize your character and level up and things. And implementing the menu system nudged me forth into finally rewriting the input system (more on that shortly).

Secondly, "Mechanics derived more from jRPGs" is probably a staight-out lie. Or at least a half-truth. Thing is, I am straight up tired of people just cribbing mechanics right from the d20 system and calling that their gameplay. So, a more accurate statement would have been: "Mechanics made up by me". I suppose this might constitute as throwing down a gauntlet, but for a genre consistently described as being the pinnacle of "gameplay over graphics", the mechanics tend toward similarity more often than not.

So, the new input system. Long story short, instead of each game state having to take into account keypresses, there's now an overarching input system that translates input into a string. Instead of having to say if(event.key.keysym.sym == SDLK_LEFT), I can now just say if(input == "left"). If shift is held down, it either capitalizes the letter where appropriate, or adds S to the front of it. If ctrl is down, C gets added to the front. If alt, M (for meta. Yes it makes perfect sense, just go with it). This simplifies things greatly when it comes to compund inputs. It also makes accessing items off a menus much, much easier programmatically. Instead of having to convert keypress inputs into an integer, then access the data at the right location, I can just iterate over the array and match the input letter with the item letter. It also makes editing the config files (which I will program sooner or later) much easier, as well as greatly simplifying the code for the "Help->Keybindings" command.

And now, in lieu of more content, screenshot time!

Human Warrior fights Goblins

Elven Mage faces off with a Goblin

Halfling Thief appreciates the randomly-generated level

The stats pane is deprecated. I'm probably going to put it on the bottom of the screen. And it isn't going to have every stat on it, but the more important derived stats (HP, MP, ATK, DEF), and XP  out of ToNextLevel (TNL). There will be a separate, more detailed stats page with a full report.

Finally, a list of things to implement before I consider the game v0.1

• More monsters than just goblins (trivial, enemies already loaded from data file)
• Menus: class choosing (on levelup, when starting a character), race choosing
• Enemies attack you as well (trivial)
• Levelup capabilities
• Respawning, dynamically generated enemies

For v0.2, I'm looking to have classes unlockable as you level, a multi-level dungeon, and the save system, among other things. Yes, this is getting ahead of myself.

Motivation

This is not the first game I've tried coding, and I dearly hope it is not the last. It is, however, most likely the furthest, most cohesive effort I've put together thus far. This is hardly surprising, because each of the proto-games I've made up to now have had similar backing.

And yet, invariably, my attention starts to wane eventually. I remember how much fun playing videogames is, or a fantastic new design idea jumps into my head and I feel as though that would be a more worthwhile project. Currently I'm avoiding purchasing Dragon Age: Origins due to the fear that it'll suck me right back out of this programming groove I'd only recently re-found (Borderlands managed to keep me from programming anything for over a week).

I ask myself what, ultimately, am I trying to do with this game?

I'm making a roguelike. As such, there's features it will have that can be described in terms of things other games have done already:

• Permanent character death
• Random dungeons
• Persistent dungeons
  
• Plenty of class-race options
• Lots of different enemies
• Magic/abilities
• Tons of items
  

That's well and good and all, but it's not exceptionally exciting per se, at least from a creation aspect. The reason being is that it's been done before, loads of times, in many/most other games in the genre. I can't speak for everyone on this, but I know that one of the main motivations for me to want to make a game is to take something I already like and make it better, or at least add some more features.

Here's an incomplete list of mostly-unique things about this particular roguelike:

• Multiclass characters
• Mechanics derived more from jRPGs (Final Fantasy, etc.) than tabletopRPGs
• Randomly-generated world
• Challenges that scale appropriately in difficulty
• Mostly random towns
• Acceptably realistic wilderness
• Varied, intricate item generation

Upcoming articles will have more to do with the second list than the first.

When both lists are reasonbly checked-off (i.e. implemented in the executable), I will consider the game v1.0. This is a very long way off. I'd estimate that the game is currently at around v0.0.7, and it's been around a month since I started (I forget the exact date). I'll call it v0.1 when I implement the message system and an attack command, because these are rather basic low-level systems that need to be implemented before I can rationalize giving the game any completion status.

I'll probably start releasing the game when I consider it v0.5 or so; where there's something that has a smidge of depth to it that's reasonably playable.

One fun Item

More and more I'm thinking about using a more Diablo-style magic item system than your typical roguelike, one in which the term "loot" might get passed around from time to time. This will all require me to implement items in general, but that's a task I'd have to go about doing anyway.

The plan then is to define various item types and base statistics which can then be modified by various adjectives. A semiinteresting consequence is that these adjectives can be magical or mundane, and these all will add up to some rather verbose item names, i.e. a Flaming Vorpal Sharp Iron Longsword of Balance and Pestilence.

On identification, the basic aspects of an item would be available at first glance; taking the above item as an example, on the ground the item would read "metal Longsword". After an Appraisal, something which should take a short but non-negligible amount of time (around a minute), the extent of the item's physical properties would be revealed, so the aforementioned sword would now show up as a "Sharp Iron Longsword". Depending on a character's sensetivity to magic, the item's magical nature can be known as early as seeing the item on the ground, or even from a distance if the item in question was of artifact-level power. At whatever point the item is revealed to be magical, the item's name changes color to whichever tier of power it belongs to. At that point, an Identify spell (available on scrolls, from the players' spellbook, or from some NPCs in town) would need to be cast to reveal the exact nature of the magic item, even though its effects have been benefiting the player from the time they equipped it.

A part of me thinks it could be interesting to have there be no easy identify - no Deckard Cain to tell you what things are for a negligible fee or less - and have the properties of the item revealed as the player's character observes their effects. But then, there would be little benefit to doing so, and the process of rubbing various combinations of weapons and enemies together would be more tedious than imaginitive, even though the process would in most cases be fairly quick (i.e., it's a simple matter of identifying Volcanic weaponry as it tends to set things on fire), and thus would be a good deal of work on my part for very little if any benefit on the player's part.

Have some Class, man

So I've been thinking more recently about game design rather than game implementation, which I suppose is a pretty good direction for things to take.

The next step is to make the combat system, and there's several ways I can start this.

1. Program the "attack" command; add "if enemy in tile you're stepping on, don't move, but attack", program the attack routine. Right now I'm thinking damage should look something like C*(A*ATK-B*DEF)^2 +- 30%, which is obviously not set in stone.
2. Program a "messages" subwindow to display "[Player] hit [Enemy]. [Enemy] missed [Player]" stuffs. Pretty straightforward, the trickiest bit is going to be knowing when to stop scaling the window that displays across the top of the screen. Actually it'd be pretty straightforward with a fixed-width font; when adding characters to a Message string, keep track of the length on the current line, when length > number_of_characters_that_can_fit_on_a_line ((screen_width - status pane width)/pixels_per_character), back up until a space is found, change the space to a newline, keep going until a fixed number of lines, prompt the player for more. The most annoying bit then is going to be handling the "more" input, but I'll just make it loop until the player presses something for now.
   
3. Add enemy "AI". At the moment I'm going to start off with a simple "always move towards the player" method which will generally keep enemies stuck in rooms, but occasionally allow them to come into a room from some adjoining hallway. It's also simpler than "if in sight of player move towards" both in terms of implementation and computational complexity (no need to scan what each enemy can see), so that's pretty cool. Also would need to add an "attack" check to enemies, but that's trivial enough to keep this nondependent on 1.
4. Leveling a character up.

#4 is the sexiest-looking, so I'm wanting to do it first. It also has a bunch to do with one of the real features of the game, the class system. And being able to make characters of multiple classes.

The player will start being able to choose from one of three to five basic classes like Fighter, Mage, Thief, and with each level up, the player chooses which class to put the level in. After meeting certain prerequisites, the player will be able to choose from new, more powerful classes with better stats and/or different skills, i.e. Knight, Ninja, Wizard, Necromancer, Ranger, and so forth. There's three ways I'd like to go about this:

1. New characters start choosing from base classes; unlock new classes as they level up, and may add levels in any class they have unlocked (allowing for Figher3/Thief2/Mage2 characters)
   
2. New characters start choosing from base classes; unlock new classes as they level up; may change into other classes a la Final Fantasy V, keeping levels. Class changes might be allowed in lieu of leveling up, but more likely will be allowed in safe locations. Or in the middle of a nest of spiders, but as it would take several hours it wouldn't be the most tactically-sound idea
3. New characters start choosing from classes unlocked in previous playthroughs, may add levels in anything ever unlocked

Because I'm weak, and can't make up my mind decisively about which'd be best, I'm thinking I'll have three different game modes. #1 will be Normal, #2 Alternate, #3 a sort of PowerMode just-for-fun type thing. Naturally, they'll all have their own high-score list, as converting the difficulty between them would be difficult and probably meaningless, or just straight up wrong.

In order to make things work across modes, I've thought of some (of what I feel are) interesting mechanics.

When you gain a level in one class, you get behind-the-scenes points in several categories. For example, instead of needing to be Fighter5 in order to access the Knight class, you need 5 points in the Warrior sphere, and every time you level Fighter you gain 1 point in it. This allows multi-class upper classes (like a Spellsword, Hunter, or Bard) in Mode2 (where you have no more than one class at a time), and greatly streamlines the unlocking of new classes (why can't a 200th level Fighter be a Paladin when a Fighter5/Knight10 can?).

Gaining new spells is something I'd like to have happen at each level. To this end, something similar to the class progression will be used. When you gain a level in a class, you gain percentage points in one or more skill disciplines, and when those points exceed a certain threshold, you can choose a new skill or two. For example, a Wizard would gain 115 Black Magic and 45 White Magic, where a Priest would recieve 150 White Magic. As you add skills in each discipline, the threshold increases and the number of skills available would increase (so newbie Mages can't pick ApocalypseIV as their level 1 spell, but could after mastering 24 other spells). I like the notion of picking your spells at regular intervals because it relies less on random chance than finding spellbooks. Never finding attack spells for a character would doubtlessly be intensely frustrating to most aspiring Wizards.

Vision - II

More adventures with keeping track of where things are.

Redid LOS algorithm with doubles instead of ints, which doesn't actually affect much of anything, other than where I do my casting to make the compiler stop warning me about it. Ah well, it only took five minutes.

My other hilarious problem came about when I got into circular definition funtimes.

I want the Character class to be aware of the Map class, so it can have a pointer to the Map it's on, so it can get Tiles on the Map as part of its visibility subroutine. Fine, I declare Characters after Tiles.

I want the Tile class to be aware of the Character class so it can have a pointer to the Character standing on the Tile, so it can tell Characters wanting to move onto the Tile whether the position is occupied or otherwise. Doable, just declare the existence of the Character class before implementing the class; as long as I only need pointers to it, it works out okay.

I also want to draw the single topmost object on the Tile, in the order of Character, Item, floor. This lets me cut down on managing drawing the player, drawing the tile, drawing enemies if they're in sight etc. and just draw what's on any given tile. This also keeps me from drawing several tiles over another, which is ugly because the non-colored space on each letter is transparent, so you can see the floor through the player. (Why not leave the black background on each Image and just draw Tiles then Items then Characters? Because then the 3D engine would look odd, silly)

PROBLEM: the draw() routine for the Character class has yet to be defined, seeing as we've yet to implement it, having only declared its existence. Can't I just declare the Character class before the Tile class? No, because then I'd run into similar issues within Character's implementation, only many more times over, seeing as how heavily several functions in Character rely on the Map class, which has a 2D array (vector) of Tiles, and Map also uses Tiles' functions. [From here on out, when I say array, assume I mean vector. I don't explicity say vector because of the Math and Physics associations they have, and I rather like those things too]

So, not too horrible, as it's only one function, and it's a function that most of the classes so far have, along with a member of the Image class (which holds several SDL_Surface*s and deals with scaling and recoloring them, very handy). So I figure, I can inherit both of those from a new base class that just has an Image and a basic draw() routine, and use virtual functions to handle the Images differently depending on the class. Turns out that you can't declare a class's base class without also implementing the class; so I was back where I started. Then an ingenious idea hit, use polymorphism. This would've been fantastic, if Visual Studio didn't forget how to use virtual functions for no apparent reason (either that or I'm doing it wrong but no I'm not shutup), and the base class pointer to a character didn't only use the base class draw function.

So, in an act of spaghettification that I wasn't particularly looking forward to, I declared the Tile::draw() function and then implemented it after the Character implementation. In the separate character.h file. Oh goody.

On further reflection (i.e., typing this entry, a.k.a. the entire reason I'm writing this down in the first place), the polymorphic approach should work, and I can't think of why it doesn't. Trying it again - I first re-read my references and run the debugger at the point at which I call the polymorphic draw() - I try making the base class' virtual draw() a fully virtual function, so it doesn't ever to execute. Turns out that it uses the base draw, even though the Character class redefines draw and has a virtual pointer to it, because the redefinition takes place after the point at which the base->draw() call occurs. So in short, it's an extension of trying to use Characters' draw function without declaring it, only without the compiler errors.

Has no one else needed to do something like this? Oh well, back to the spaghetti. On the plus side, ugly code is better than code that doesn't work, so at least I've got that going for me...

So what did all that have to do with vision?
Not altogether too much, but it does let me do some cool things. For starters, differentiating between visible or out-of-sight tiles is doable without needing to store visibility data on the tiles themselves, which would be useless data most of the time, given the probably small percentage of tiles on a given Map that would be visible at any given time. Secondly, it removes the need to keep track of what has been drawn on what tiles already; it's implicitly assumed that each tile is only drawn once (and would draw the same thing each time it's drawn). Thirdly, keeping track of which enemy is on a given tile greatly simplifies finding which enemy you just attacked, or which ally you just healed, etc.

Vision - I

Finally got a Line of Sight (LOS) algorithm implemented.

My first quick-and-dirty "ingenious" idea that struck at around 11:00 at night (PROTIP: you should never code when you're tired, even though I'm going to break this tip (again) as soon as this post is done) was to use a filling algorithm in the vein of breadth-first-search, i.e. starting from the tile the Character is on, giving each tile considered a value of the current tile's value+1 and pushing on a priority queue until the current value was greater than the player's LOS distance. Then I realized that I'd need to increase the value by sqrt(2) for diagonal values, unless I wanted the player to be able to see in a square.

It wasn't until AFTER I'd finished coding it that I realized that this would let the player's sight "spill" around walls. By this point, it was nearly midnight, and 8am class was beginning to rear its ugly head at me from the future, so I put my code, my computer, myself to sleep.

My next idea (a.k.a the right way how to do it) was to get a series of points in a circle around the player at a distance R, then draw lines from the player to those points, stopping if a wall interuppted a line. Take all the points a line went through and store them in an array (STL vector, naturally) associated with a Character. Thus we have all the Tiles that any given Character can see, and from there we can either show the player visible tiles, or see if an enemy can see the player.

As an aside, I'm wondering if there's a better way to show the duller tiles that are out of the active visibility field than storing a second surface for each image color multiplying by a down-factor (20% darker?), or storing a second surface at a slightly smaller size. For now I'm going to implement the second image with a color multiply, but I'm thinking out loud here. And scowling to myself, knowing "there's gotta be a better way".

On LOS: my first instinct was to repurpose code I'd written earlier for a different project that would draw lines circles with pixels, changing the "putPixel" faux-routines I'd written into adding Tiles to a vector and returning it (I didn't have a putPixel function written, but that was thanks to the horrendous overhead of the thousands of function calls it wound up making; something the inline command failed to help with at all). This, of course, led to several issues.

Firstly, the lines would start inside of walls sometimes, and not draw in certain directions others, but only in some positions. Quickly, I realized it was because the particular implementation of the Bresenham algorithm I was using didn't necessarily draw lines from the point 1 to point 2, so I had to rework it a bit so it would work without swapping the points.

Still, though, the visible field it gave me was completely off. The line-drawing algorithm worked perfectly sometimes, so that probably wasn't it. It turned out to be that in my reimplementation of the circle-drawing algorithm, I hadn't referred to the code that actually produced a working circle, but instead some notes on circle geometry that hadn't worked out so well at all (but looked convincing on paper). How I was doing it was dividing the circle into 1-tile-high slices from j = y - R to j = y + R and using the points on the left and right edges of each slice. The problem was, I was taking the width of each slice as w = 2*R*sin(acos((R-j)/R)) which anyone can see will cause problems. For those who actually care, the correct width was 2*sqrt(R^2-(R-j)^2).

That worked much better, and gave me a contained field in the shape of a circle that the player could see and moved consistently with the player. All well and good, but it had several holes in it near the y-axis for no apparent reason. Then it clicked that while the slice-based algorithm worked acceptably well for drawing full circles with rectangles, it only considered one point per horizontal line, which left noticable gaps near the top parts of the circle, where the slope of the tangent was much flatter.

So I buckled down and looked up the "Bresenham" circle-drawing algorithm (not actually designed by Bresenham, but similar enough to his line-drawing algorithm that people give him credit for it). The version that I shamelessly stole off Wikipedia is fairly inelegant to my eyes (I much prefer minimizing lines of code; ironic then that I'm writing a roguelike), but I so far cannot be bothered cleaning it up with for loops instead of eight explicit putpixel functions (on reflection, an idea for which has just struck; it also involves bitwise operations, which are pretty as far as I'm concerned). For LOC, it works significantly better, and gives a mostly-full circle (dropping, amusingly, only the 45-degree angles).

Now I'm off to improve it using floating-point values for x,y offsets of the points on the circle, which I'd put off until now because I'd been reimplementing the way Tiles displayed themselves and their contents. I.e., I finally started giving Tiles contents.