Pyramids

"Most people who graduate with CS degrees don’t understand the significance of Lisp. Lisp is the most important idea in computer science." -Alan Kay

"Most software today is very much like an Egyptian pyramid with millions of bricks piled on top of each other, with no structural integrity, but just done by brute force and thousands of slaves." - Alan Kay

...and that's the guy that invented SmallTalk!

Everybody is so concerned about carving giant stone blocks, and mixing sand with muddy clay to make mortar.  While that's going on, a few of us have discovered that there's a way to automate the creation of ceramic bricks.  When one of us comes back with excitement to the mud pits and passionately proclaims that there's a fundamentally better way to do things, the response is merely a passing glance of scorn at the machine, and then a lot of yelling.

"WHAT ARE YOU DOING!?  You can't make pyramids with that thing! We don't have time for this, and nobody understands what you're doing anyway!  Look at all of those turn knobbies and buttons and stuff, how is anybody expected to actually use this thing?"

"But but...  this is just a prototype!  It's just what I was able to put together in a little bit of time to demonstrate.  If we could get everybody to understand this, then we could build a really nice brick press machine, along with a brick-laying crane. Then when we're not spending all of our time making and placing bricks, we can think about better materials, and fundamentally new ways to architect our buildings!  We can smelt ore, make steel, and once we've figured that out I hear there's this concept called an I-beam that..."

"CRANES!?  Sure, maybe you can do that to lift your puny ceramic bricks, but you can't make a machine that will lift 10 ton blocks!  It'll topple over!  We have a team that uses the time-proven tradition of pushing our blocks on rolling logs up massive earthen ramps.  THAT'S the way to construct great buildings.  We've seen what happens when you try other ways - the folks over in the PHP kingdom make all of their stuff out of lumber.  Sure, it's quick to harvest, cut, and build, but you know what happens when their buildings catch fire."

"No!  You're missing the point!  Stop thinking in terms of giant stone blocks, or even lumber, and look at what we can do with steel I-beams.  Once we have the infrastructure in place to manufacture them, we can then create buildings ten times as tall as our pyramids, in 10% of the materials, in a fraction of the time, with significantly less slaves.

"BWUAHAHAHA!  You expect us to believe that?  Preposterous!  Look, we have work to do, if we don't get back our competition will crush us.  Why don't you use your silly brick machine to make a nice kennel for the royalty's hunting hounds?"

Status Update

It's been a while since the last post, and there's been plenty of improvement.  Here is a brief list of things I've worked on in the last couple of months:

• The "scent maps" aka "dijkstra maps" discussed in the last blog post.
• Predator/prey relationships based on each entity's dijkstra map.  Predators are attracted to prey, prey are repelled from predators
• Reproduction.  Entities of the same species with opposite genders can reproduce, given a sufficient attraction factor.  After gestation, a new entity is born.  This isn't really obvious because when I prototyped it, the gestation time was instant, and pairs that can mate were almost always attracted to each other over anything else - you can guess how that turned out.  After creating an attraction factor and a gestation time depending on the species, it has made the reproduction system rarely noticeable.  Unfortunately I don't have any infant sprites yet, so offspring look fully mature for now.
• Simple jobs - characters can now build walls (left click for now), and remove parts of the terrain (right click for now).  The characters are attracted to jobs based on the jobs' dijkstra maps.
• Underground view - You can "slice" the terrain view using the middle click on a location, also spinning the scroll wheel up and down adjusts the slice level up and down.
• Terrain overhaul - There are new terrain sprites with a 2:3 iso ratio, making most of the back slopes visible.  Along with that, each type of terrain now has 16 different sprites instead of 5, making much more cohesive terrain contours.
• Minimap - This renders pixels representing the terrain, and works with the "slice" feature mentioned above.  It doesn't respond to clicks yet, but I would like to make it center the terrain view on the given location when clicked.

Thoughts about game entity AI

I've been thinking a lot about how to implement the behavior of entities (people and creatures).  Many mainstream strategy games involve the player giving specific orders to everybody under their control, and the entities subsequently use an A* path-finding algorithm to navigate toward the area indicated until they are in range to do their assigned task.

One important aspect of A* is that it requires a specific destination.  That's fine for giving specific orders to entities, but I want to avoid making a micro-management game.  I'd rather have general commands like "I need people to hunt over here", "cut down lumber here", "build a wall around this area", "plough these plots and then plant cabbages"...  Then each entities decides what to do, given several potential jobs to do, hazards to avoid, and their own set of skills, likes, dislikes, fears, etc. 

From what I understand of AI, this kind of behavior boils down to the following:

1. Determine what options there are to choose from.
2. Calculate a "score" for each option.
3. Choose the option with the best score.

If I were to use A* path-finding, the entities would have to first choose a destination.  This could be done by looking up choices in close proximity, but that would exhibit what I call the "great wall" problem - An entity may find something interesting to do within a distance of just a few steps, and decide that it is the most compelling goal.  However, if there is a large barrier in between (a wall, a deep river, etc), it will potentially take the entity much longer to get there and finish the task than something else that is a further distance away.

One possible solution would be to divide the map into "sectors" of some sort, so that opposite sides of a wall are in different sectors, but then there's the problem of splitting, merging, and otherwise updating the sector table as the entities modify the environment (mine through the mountains, build walls, et. al.)

The other possible solution is to have the decide-what-to-do function do a traversal of the area around the entity to find things of interest (probably using Dijkstra's algorithm), but that defeats the purpose of A*, since its whole point is to do an optimized traversal toward a specific destination (A* is really just a modification of Dijkstra's).

So at that point in my thinking, A* was out, and it seemed like Dijkstra's might work.  Dijkstra's algorithm does an even breadth-first traversal.  It could be implemented to take a number representing how much depth to explore, then collect information about things found within the explored space.  The entity could then take the list of potential things to do, along with the path to each thing.  It would make a decision based on some math to score each option.  If the chosen destination is adjacent to the entity's current location, do the task (attack, build, mine, sow, whatever), otherwise move along the calculated path.

Let's say there are multiple things about an entity's environment that will influence its behavior.  For example, assume that an entity can have a "hunter" skill.  Further assume that there exist a hostile creature (say a dragon) that can be successfully hunted by a group, but is likely to defeat a lone hunter.  How does a hunter know whether it's a good idea to pursue the dragon?  There's a risk/reward balance to be struck here - certainly it would be a good thing to fill the storehouse with cured dragon steaks for the winter, but it would be a bad thing to be roasted by the dragon.

Using the traversal algorithm, the decision algorithm invoked for a hunter could determine that there are multiple other hunters in the area.  It could do some math to determine how likely the hunt is to succeed, and could make a decision to advance or retreat (maybe throwing in the specific hunter's fear of dragons and taste for dragon steaks - fight or flight syndrome).  The advance or retreat would further influence the other hunters' behavior.

Ok, so far it's feasible.  The advance just means taking a step toward the dragon, as previously determined by the path-finding algorithm.

But what about the retreat?  The entity has a clear indication of how to advance, but not necessarily how to retreat.  It would be nice to have an obvious way to determine how to get away.

Somewhere in this thought process, two things came to mind, both related to emergent behavior.  Years ago I did an implementation of Boids in Python.  Also, at some point in the past I read a blog post about how the pac-man ghosts' behavior was implemented (sorry, no link, I don't remember where it was, but it's been discussed quite a bit, google around for more info).

For more info about Boids, read the wiki article, but basically it is an algorithm that simulates a flock of birds by emergent behavior - Each bird's movement is influenced by three factors:  try to maintain general proximity to the center of the flock, try to match the average velocity of nearby birds, and try to avoid immediate proximity of other birds (avoid collisions).  Giving each entity a few simple rules results in some really interesting overall behavior of the flock.

The discussion about implementing ghost behavior in pac-man centered around the concept of pac-man leaving behind a "scent" that dissipates over time.  In persuit mode, the ghosts would simply move to whatever adjacent location had the highest "scent", or make a random decision at intersections if there was no scent to follow.  In retreat mode, they would do the opposite.

So this lead me to think, what if every entity in the game has a "scent".  I think I would do it different than the pac-man example - the scent would be calculated by traversing a certain distance away from each entity, periodically updated to account for changes in entity locations and how the environment can be traversed.  Then, each entity can make immediate decisions based upon calculations made to the scents around them.  In the hunter example, each hunter would observe the scents for each location adjacent to their own.  Assume that a hunter finds that the dragon scent is strongest in front of him.  If there is insufficient scent from other hunters, the math that scores the location will determine that it is not a compelling choice.  Further, the most compelling adjacent location will be the one that leads further away from the dragon.

I think that the "scent" concept will work for a variety of things.  People could enjoy being around each other, but avoid crowds.  Somebody with skills as a miner and a blacksmith might have to decide between working on a project at the anvil or hollowing out a new found coal vein.  I imagine that there could be a situation in which one entity really doesn't like bunnies, but bunnies really like him, so in the absence of hunger or other such pressing needs, the bunnies end up chasing him around.

There is still plenty that needs to be worked out.  The concepts of "likes", "fears", etc., and how those attributes influence the scoring logic will be interesting to work on.

Terrain Discovery

I implemented terrain discovery based on the people's locations.  Right now it just uses a cheap range calculation around the person's location, so it is possible for them to see things even if they don't have a line-of-sight on it.

As always, find the latest revision at http://bitbucket.org/willismichael/terra-incognita

Here is the function (found in /src/model/update.clj) that determines the visibility from a given location:

(defn- visibility [[x y z]]
  (let [h-range (range -6 7)
        nodes
        (for [dx h-range dy h-range dz [-2 -1 0 1 2]
              :let [x (+ x dx) y (+ y dy) z (+ z dz)]
              :when (< (+ (* dx dx) (* dy dy) (* dz dz)) 36)]
          [x y z])]
    (zipmap nodes (map (partial world-get @wrld) nodes))))

It's quite terse, but don't let that scare you.  The first line takes a location as a parameter, and deconstructs it into x,y,z coordinates.  Next, it creates h-range, where (range -6 7) is just short for [-6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6].  Those are the horizontal coordinates relative to the viewer.  The "for" statement evaluates for every possible combination of relative coordinates that we're interested in, from -6,-6,-2 all the way to 6,6,2.  These are filtered using the distance formula (so that visibility has a radius of 6, rather than being a square)

Finally, all of the coordinates that meet the criteria are used to pull information from the world.

One thing you could play with is the visibility range and radius.  For example, if you want to change horizontal visibility from 6 to 20, change (range -6 7) to (range -20 21), and change 36 to 400 (that's 20 squared).  Or, if you want them to be aware of several layers in the ground beneath them, change dz [-2 -1 0 1 2] to dz (range -20 2)

Random Wandering Characters

After looking for some free artwork to start from, my brother and I found some nice sprites from these sources:

http://www.reinerstilesets.de/
http://units.wesnoth.org/1.10/pics/

I took some plants for reiner's site and joined them into a single spritesheet, and my brother used some of the unit sprites from the Wesnoth community contributions as starting points.  I also drew some slopes and threw together some code to place the slopes and make the people wander around aimlessly.  Here are the results:

There are two known bugs:

1.  There is a somewhat rare bug that crashes the program if one of the characters has nowhere to go (for example, if they are surrounded by trees).  If that happens, just try running it again.  I'll fix that soon.

2.  The way that they negotiate slopes is kind of weird.  They don't really consider the direction of the slope when they choose to climb up or down, so you may see them hop up the bare side of a sloped piece, or sometimes it looks like they float in the air because of being "on top" of a slope...  yeah, it needs some work, but whatever.

Right now the male dwarf is the only one animated.  The rest have spritesheets ready for animation, but each character's frames are just copies of a single sprite:

 

Homework:

Download the latest revision (As of this post it is https://bitbucket.org/willismichael/terra-incognita/changeset/53da946faac1 - or you can always get the latest version on the project main page: https://bitbucket.org/willismichael/terra-incognita)

Run it, and report back how many frames per second you are getting, and what kind of hardware you have (cpu/memory/video).  I'm trying to figure out a way to improve the performance which is quite dismal since I've just been hacking this together. 

Pick one of the characters that still needs to be animated.  Use Gimp (or some other image editing app that supports transparency).  Follow the pattern shown by the male dwarf to complete the animation frames for your character. (note the direction that the dwarf faces on each row).

Extra Credit:

Monkey around with the code a bit.  Try opening src/entities.clj - you can arrange a different party by modifying the place-entities function.  You'll see that it creates a list of people by calling another function called "person" multiple times.  The "let" block at the top calculates the center of the map, but it isn't really necessary.  Look at the definition of the "person" function above, it takes a reference to the world, x/y coords, race, and gender.  So an example that places them in fixed coordinates instead of relative to the center of the world would be something like this:

(defn place-entities [wrld]

  [(person wrld 50 50 :dwarf :female)

   (person wrld 50 52 :dwarf :female)

   (person wrld 52 50 :dwarf :male)

   (person wrld 52 52 :elf :male)

   (person wrld 54 54 :elf :female)])

Also you could play with the "person" function.  Right now some of the values in there don't do anything, but walk-speed does work.  It is a number representing how many tiles they can walk per second.  It currently picks a random number between 1.0 and 1.5 like this: (+ 1.0 (rand 0.5)), but you could try erasing that expression and replacing it with a fixed number, or writing a different expression.

One thing that could be interesting is making the race determine the walk-speed, like this:

:walk-speed (cond

  (= race :elf) 2.0

  (= race :dwarf) 1.0

  (= race :human) 1.5)

The function "cond" takes pairs of conditions and corresponding expressions.  It finds the first condition that is true, and evaluates its expression.  In this case the expressions are simply numbers, but they can be more complex:

:walk-speed (cond

  (= race :elf) 2.0

  (= race :dwarf) 1.0

  (= race :human) (+ 1.5 (rand 0.5)))

 In that, the elves all get a speed of 2.0, the dwarves all get a speed of 1.0, but humans get a random speed between 1.5 and 2.0 

Don't get too attached to any of these functions, most likely as the project matures most the code will probably get rewritten and refactored to the point that it doesn't resemble the original at all.

Landscape Generator

After a bit of research I decided to try using an algorithm called Simplex Noise to help generate the landscape.  I found a nice implementation here:  http://toxiclibs.org/ . Simplex noise is a function that takes 2, 3, or 4 numeric parameters, and results in a number between -1 and 1.  The terrain generator uses the coordinates on the map as input to the 2-parameter simplex function, and uses a multiple of the result to determine the altitude of that place on the map.

Then, to decide what kind of terrain to put there, the terrain generator creates a variable called "adjust", equal to the altitude plus a multiple of the 3d simplex noise.  If the resulting number is greater than 16, it places stone.  If it's less than 12, it places grass.  Otherwise it places dirt.

Here is the code that determines the altitude and what type of block to place:

let [z (+ 11 (int (* 10 (SimplexNoise/noise (/ x 32) (/ y 32))))) 
     adjust (+ z (* 4 (SimplexNoise/noise (/ x 4) (/ y 4) (/ z 4))))
     type (cond (> adjust 16) :stone (< adjust 12) :grass true :dirt)]

Later,  grass blocks have a 40% chance of getting a tree on top, dirt blocks have a 10% chance of getting a tree on top:

(cond
  (and (= type :grass) (> (rand) 0.6))
    (put-block new-world x y (+ z 1) :tree)
  (and (= type :dirt) (> (rand) 0.9))
    (put-block new-world x y (+ z 1) :tree))

The results:

 
There is also a new ability to use the arrow keys to scroll around the map.  Don't use the mouse, it makes the program crash ;)

Check out the latest revision:  https://bitbucket.org/willismichael/terra-incognita/changeset/64809b60353d

Homework:

Edit src/world_gen.clj - since it's a rapid prototype, the code is a bit of a mess, but you can play around with the numbers to see what happens.  Specifically, try messing with the numbers that are passed to the simplex noise functions, you'll see different "clumping" of terrain types, and different slopes.  Just change one number at a time, because some of them can cause the altitude to go out of range, which can crash the program since there still isn't any error checking.

Extra credit:

Edit media/blocks.png with Gimp.  Try adding a new terrain type or plant.  Your new sprite should go next in the same row as the rest, since the renderer just uses a numeric index to figure out which sprite to draw.  Edit this code in world_gen.clj to add your new block:

(def blocks {
  :dirt 1
  :grass 2
  :stone 3
  :tree 4
})

The number next to each keyword indicates where the sprite is found on the spritesheet.

Then edit the terrain generating function to use your new terrain or plant.  For example, you might edit the conditional statement that places trees so that it also puts a bush:

(cond
  (and (= type :grass) (> (rand) 0.6))
    (put-block new-world x y (+ z 1) :tree)
  (and (= type :dirt) (> (rand) 0.9))
    (put-block new-world x y (+ z 1) :tree)
  (and (= type :dirt) (> (rand) 0.8))
    (put-block new-world x y (+ z 1) :bush))

(This is assuming that you added :bush to the "blocks" above)

 Again, just do small changes at a time, and test each change.  That way if there are any errors you can undo your last change and try again. 

Leave a comment with your results!

Prototype

Sorry, I've been busy and most of the work that I have done isn't really exciting to show off. While I was prototyping some code to display graphics I was getting a REALLY slow framerate (using Java's built-in Swing library), so I switched to a different graphics system (Slick2D) and I'm playing around with storing all of the cubes in a nice compact 1-byte-per-cube way, and then the "entities" (people, animals, workbenches, anything that needs more behavior than a simple cube) are stored in some other data structure. That way the world could be reasonably big (say 4000x4000x50 cubes) in less than a gigabyte of memory.

I thought about breaking the world into zones that only get loaded as needed, but it's a lot easier to just store one giant world instead of dealing with a world composed of a bunch of smaller zones. Maybe one of these days I'll get the zone-based solution done, but for now I'm trying to "do the easiest thing that could possibly work".

The good news is that I pushed it to bitbucket:

https://bitbucket.org/willismichael/terra-incognita

There isn't an official release in the downloads section yet (probably won't be for a loooong time), but you can download the work-in-progress by going to the "get source" menu over on the right. Later if you want to contribute to the project and send your changes back to bitbucket, you'll have to use a program called "git" to do it, but we can discuss that later.

I think the next step is to play around with landscape generation. For now it's just a flat plain of random cubes, without any people, plants, animals, items, furniture, etc. (Even though there is the beginning of a sprite sheet for some of that stuff).  Like I mentioned before, I'm breaking up the world definition into two components: cubes and entities.  When I do add the entities, they'll be able to have more interesting attributes, like this:

{:name "Rolff Stonefist" :race :dwarf :gender :male :location [17 15 7] :strength 53 :endurance 47 :hunger 0.7 :thirst 0.3 :inventory { :feet {:name "black boots" :durability 37 } :legs {:name "leather pants" :durability 31 } :torso {:name "wool tunic" :durability 23 } :shoulders {
:name "backpack"
:capacity 12
:contents [:apple :bread :flint :torch]} :hands {:name "mining pick" :durability 45 } :experience { :miner 37 :blacksmith 11 :forager 7 } :likes { :stone 0.51
:steel 0.47 :meat 0.53 :bread 0.35
:leather 0.27 }
:dislikes {
:rabbit 0.47
:crowds 0.65
} :fears { :snake 0.76 :being-alone 0.35 } }
This is just off the top of my head, I'm sure it will end up a lot different from this, but with this idea we can make some functions to create random characters based on templates, like (create-random :dwarf) (create-random-creature :forest) (create-random-creature :desert)... Then there can be some functions that dig through the entity data and do interesting stuff, like find/eat food if its hungry, find/drink water if thirsty, fight-or-flight syndrome when scared, look for something interesting to do (e.g. take an available job) if basic needs are met.

I'd like to make it so that things in inventory are also entities, so for example when something gets dropped it just gets removed from inventory and added to the world at some location right by the character. I'm still thinking through exactly how to do that, but if done right it means that there's no need for specific functions for every individual type of thing that can exist in the world, it's just a matter of making an entity and giving it the right attributes and like magic it works.