Tuesday, February 26, 2013

Choosing colors for your Roguelike

If you're making a roguelike you need to decide what colors to use. You could stick with the original 16 colors or you can use hundreds or thousands of colors. I don't know much about colors and color schemes but I have some advice on choosing colors for a roguelike. For my 2012 7DRL, I rule, you rule, we all rule old-school Hyrule, I followed three simple rules about color:

  1. The hue should match the real world color. That is; red things should be red and green things should be green.
  2. The saturation and brightness should match how important something is. If it's trying to kill you or it can save you then it should stand out as a bright color. If it's just background - floors, trees, walls - then it should be mostly gray or black so it doesn't get your attention. You can only notice so much at once and you should notice the important things first.
  3. Subtle variation in color is a good thing. Some variation makes large blocks of trees or water look better but too much variation and shading makes it hard to tell if the color is relevant or not. In iryrwarosh, each tree has three different colors. Water, lava, and sand also had some variation. The variation was subtle enough to break up the monotony and allow things like animated water and lava. Possibly too subtle, but that's just fine with me. Just don't overdo it; even if two trees are a slightly different shade of red or green, you should still know they're the same thing.

Overall I'm very happy with how iryrwarosh looked and I think it's due to following these three guidelines. It did take some time to tweak the colors, but it was really worth it. I plan on following the same guidelines this year.

As a bonus, here's the ActionScript that I use to make a color with a specific hue, saturation, and value.

Saturday, February 23, 2013

A* algoritm in ActionScript

Want to know the shortest path from one point to another? If you're making a roguelike then you probably do. You could use Dijkstra's algorithm, but there's an alternative that finds the result much faster. It's the A*, or A Star, algorithm. It's a lot like Dijkstra's algorithm except instead of checking the neighbors of all the currently visited cells, it just checks the neighbor of the visited cell that's the closest to the target. Of course if you already know which one is closest then you don't need to pathfind. Instead you just estimate which one is closest. Even if your estimates are a bit off, you'll still find the shortest path in much less time.

Here's an ActionScript implementation.

This algorithm needs some explanation since it was made by mathematicians - who generally suck at naming variables. That's why there's a g, h, and f cost. The H cost is the heuristic or estimated cost from a point to the end point. The G cost is the actual cost from the start point to a point. There's no need to estimate that because you only calculate this on points that you've visited. The F cost is the total of the two. By only checking the neighbors of the point with the lowest F cost, you end up - in the best case - only checking the points that are in the shortest path. You can change the getGCost and getHCost methods to cause different behavior. Maybe some points cost more to travel through? Maybe moving diagonal cost more than moving in the cardinal directions? Try it and see what happens.

The checkEnding boolean is because in my game people sometimes can pathfind to walls and obstacles that block movement.

It's mostly used for pathfinding but can also be used for carving rivers, roads, or caves during worldgen. You could also use it to tell where someone is probably going to go - useful for placing traps I suppose. Have you seen any interesting uses for this algorithm?

Tuesday, February 19, 2013

Dijkstra's algorithm in ActionScript

Dijkstra's algorithm is a useful algorithm for roguelike developers to know. It basically calculates the distance from a starting point to all other points. Once you know the distances, you can walk backwards from any point to the start. It's great for worldgen, floodfilling, ai, and pathfinding to the nearest something. Dijkstra's algorithm is also the basis for autoexplore in brogue. If you want to know "where's the nearest" of something, use Dijkstra's algorithm.

Here's an ActionScript implementation.

Note that it uses a grid to track parent nodes as well as if a cell has been visited or not. It does this for performance reasons but it's possible to keep a list or dictionary of visited nodes instead.

This implementation takes the start position, a function that verifies a cell can be entered, and a function that determines if a cell is what you're looking for. It returns an array of points from the start position to the end position or an empty array if no path was found. Using canEnter and check functions means that there's no dependancies on details of your game code - which is a very good thing. Passing in your game details means that if you want this to work with land creatures, water creatures, and amphibians, just pass different versions of canEnter depending on who's searching. And since you pass your own check function, you can search for whatever you want. Injured creatures could search for the nearest healing potion. Fleeing creatures could look for the closest tile that isn't visible from the player. Exploring creatures could look for the nearest tile that they haven't seen before. There's a lot of potential uses for this algorithm.

Saturday, February 16, 2013

Field Of View (FOV) in ActionScript

One of the simplest ways of calculating Field Of View (FOV) in a roguelike is also my favorite. There's several different algorithms but I like to keep it simple. Just check every tile within a view radius of the player. If you know how to calculate Line Of Sight, then it's very easy. If the line to the end point isn't blocked, then the end point is visible. Once you can check line of sight between arbitrary points, then it's easy.

Here's a Flash implementation. Use your mouse to see what's viewable from a location.

It's probably the least efficient way to do it - which is why it takes a second or so to calculate. It is super simple to understand and implement though. I also think it looks the best. Not only can this be used for seeing which tiles are visible from a specific tile but it can also be used for seeing what's affected by an explosion or other effect.

Once you have performance problems you can switch to a more efficient algorithm or rely on caching.

Thursday, February 7, 2013

Line Of Sight (LOS) in ActionScript

One of the simplest algorithms in any roguelike is line of sight (LOS). It's basically drawing a line from one point to another and seeing if anything obscures it. Here's an Actionscript implementation of the Bresenham line algorithm (invented in 1962!).

It's not super obvious what's going on. Basically, figure out which direction the line always goes, and how often it goes in the other axis. Then go.

This is the basis for simple field of view (FOV) algorithms and is a quick and easy way of seeing if a tile, item, monster, or event can be seen by the player or another creature. It can also be used to calculate where a projectile will go, corridor generation, or simple pathfinding in open spaces.

I'm sure there are low-level ways to make this perform faster like bit shifting or breaking each octant into it's own function. It could also return an iterator that calculates points as-needed. This would allow really long lines - or even infinitely long lines - while only calculating what's actually needed.

Friday, February 1, 2013

Updates to SocialRoguelike

Just a few small additions.

Apples now grow into trees, trees drop apples, and it's possible to die of starvation or lack of sleep. Wood and dirt are new items that can be picked up, moved, and used to make dirt walls or wooden doors. There's also 60 * 24 turns in a day. The from, at, and to prepositions can include times. This means you could tell your followers to "move 99 apples to the orchard from 11:00 to 13:30" if you wanted to make your own apple orchard.

Reminder: if you want to eat or sleep or do anything other than move, you need to address the command to yourself. like "@me, eat %" or "@player, sleep in my house".

Next I'm going to add seasons, weather, climate, more plants (carrots, grass, cabbage, etc), resources (stone, clay, etc), and terrain (water, mud, stone, etc). I'm not sure how much I'll get done with all the excitement of the upcoming 2013 7DRL in a month or so....