How a dinosaur is not like a tank.

A cross-section view of the elevation that a T. Rex (named Bob) will have to traverse to get to an Edmontosaurus regalis (named Gertie). Click to enlarge.

A cross-section view of the elevation that a T. Rex (named Bob) will have to traverse to get to an Edmontosaurus regalis (named Gertie). A very steep riverbank is between Bob and Gertie. Vertical axis: elevation in meters, horizontal axis: distance to goal in meters. Click to enlarge.

A few days ago I wrote about Dinosaurs, tanks and line of sight algorithms and how my previous work in modeling and simulations (M&S) for military wargames (specifically line of light algorithms) was applicable in Dinosaur Island. Today I am working on the models for dinosaur movement, speed, and what are called “least weighted path” algorithms.

You are probably familiar with least weighted path algorithms even if the term is new to you. Least weighted path algorithms are used to calculate routes in GPS units for cars or smartphones or for various internet sites like MapQuest, Google or Bing. When calculating a route there are a number of criteria to chose from. Does the user want:

  • The fastest route?
  • The shortest route?
  • The most fuel efficient route?
  • The route that avoids certain features (such as specific terrain, topography or extreme slopes)?

These options are what ‘weight’ the potential routes in a ‘least weighted’ path algorithm. For example, taking the Interstate is often the fastest route (least amount of time) but frequently is not the shortest route (least amount of distance).

Back in grad school I did my ‘comprehensive exam’ for PhD students on the subject of least weighted path algorithms. There are two very popular algorithms that solve this problem: one is Dijkstra’s algorithm (which is an exhaustive search solution) and the other is the A* algorithm, by Peter Hart, Nils Nilsson and Bertram Raphael. The primary difference between Dijkstra’s algorithm and the A* algorithm is that Dijkstra’s is guaranteed to return the optimal solution but it often takes the most time to calculate. The A* algorithm is much faster to calculate but is not guaranteed to return the optimal (or perfect) solution. In computer games we almost always use the A* algorithm because speed of calculations (especially over large maps) is more important than having the absolutely perfect route. At the bottom of this blog are links to descriptions of these algorithms and my research paper discussing an optimization of A*.

But, what does this have to do with dinosaurs and tanks?

When working on an M&S involving vehicles (like tanks) our primary concern is finding the fastest way for the tank to get from Point A to Point B. Sometimes, we want the tank to avoid entering into an area where the enemy (called OPFOR, or ‘Opposition Forces’ in military parlance) can hit it with their weapons (this is called ‘range of influence’ or ROI). This is illustrated below:

This image shows how MATE will calculate the least weighted path for a unit using roads, terrain, elevation and avoiding enemy weapons range for 'path weights'. (Click to enlarge.)

This image shows how MATE will calculate the least weighted path for a unit using roads, terrain and elevation and avoiding enemy weapons range for ‘path weights’. (Click to enlarge.)

We also want the tank to take advantage of roads and avoid swamps, rivers and ponds.The maximum speed of a tank traveling on a road is higher than the maximum speed of a tank traveling across a field. This is not the case with a T. rex or an Edmontosaurus regalis.

Another difference between tanks and dinosaurs is that as long as a tank has fuel it can go at 100% of their maximum speed (on a specific terrain) without problems. This simply isn’t the case with dinosaurs. As dinosaurs expend energy (and remember, energy is the ‘currency’ of Dinosaur Island, see: The currency of Dinosaur Island) they get tired and they can’t run as fast or as far. Also, dinosaurs run at their maximum speed only for short distances and only in extreme emergencies or at the very end of a hunt when they attack.

The illustration at the top of the blog also points out another major difference between tanks and dinosaurs: modern tanks (specifically the M1A1) has a published specification of being able to climb a 60 degree slope at a speed of 7.2 km/h (see here). That’s pretty impressive. It’s unlikely that that a T. rex could navigate a slope that steep. In the cross-section at the top of this blog we show the slopes that Bob, the T. rex, will encounter following a straight line to Gertie, the Edmontosaurus.

Clearly we’re going to need to use a least weighted path algorithm for calculating dinosaur movement so that they will avoid steep riverbanks and crevices. We also will create a table of ‘energy costs’ that dinosaurs will incur as they travel across various terrains (like swamp). These values will be used in our least weighted path algorithm.


Some links about least weighted path algorithms:

  • Dijkstra’s algorithm on Wikipedia has a very easy to follow description with a couple of cool animations to show how it works. Link here.

  • A* search algorithm on Wikipedia also has a couple of very nice animations to show how it works and pseudocode. Link here. By the way, I once sent Nils Nilsson an email asking him what the ‘A’ in A* stood for and he replied, “algorithm.” Now you know.

  • “An Analysis of Dimdal’s (ex-Jonsson’s) ‘An Optimal Pathfinder for Vehicles in Real-World Terrain Maps,‘ the paper for my Comprehensive Exam can be downloaded here.

Herbiverous dinosaurs getting along at the salad bar

What does your dinosaur eat? How much energy does he need? How much energy is produced when he is eaten?

You can select what each species of dinosaur eats on Dinosaur Island (screen capture, click to enlarge).

On Dinosaur Island you can select what each species eats. A recent article (quoted at length, below) shows why this is necessary to simultaneously maintain numerous species of large herbivores.

A new study by a Canadian Museum of Nature scientist helps answer a long-standing question in palaeontology — how numerous species of large, plant-eating dinosaurs could co-exist successfully over geological time.

Dr. Jordan Mallon, a post-doctoral fellow at the museum, tackled the question by measuring and analyzing characteristics of nearly 100 dinosaur skulls recovered from the Dinosaur Park Formation in Alberta, Canada. The specimens now reside in major fossil collections across the world, including the collections of the Canadian Museum of Nature. The work was undertaken as part of his doctoral thesis at the University of Calgary under the supervision of Dr. Jason Anderson.

Mallon’s results, published in the July 10, 2013 issue of the open-access journal PLOS ONE, indicate that these megaherbivores (all weighing greater than 1,000 kg) had differing skull characteristics that would have allowed them to specialize in eating different types of vegetation. The results support a concept known as niche partitioning, which dates to the 19th-century studies of Charles Darwin and came into its own in the 1950s with the development of the science of ecology.

A link to the article is here:


Thirst or hunger? What is more important to a dinosaur?

A drinking hadrosaur from I think the reference of the

A drinking hadrosaur from a set of 1916 German collector cards “Tiere der Urwelt” (Animals of the Prehistoric World) by Heinrich Harder, from here. (Copyright expired.)

What is more important to an animal that is very hungry and very thirsty: water or food? I just encountered this problem when writing the AI code for dinosaurs finding food and water. When ‘new’ dinosaurs are currently created in Dinosaur Island they haven’t yet eaten or drunk water so the stored values for every new animal is ‘0’. Obviously, we can, and will, change that so ‘new’ dinosaurs are created with some values (these ‘new’ dinosaurs are not ‘just hatched’ dinosaurs but rather adult animals that are created and placed on Dinosaur Island for testing purposes).

Screen capture showing a very thirsty Edmontosaurus named Gertie who is now walking towards the closest observed water. (Click to enlarge)

Screen capture showing a very thirsty Edmontosaurus named Gertie who is now walking towards the closest observable water (click to enlarge).

The above screen capture from Dinosaur Island shows a very thirsty Edmontosaurus, named Gertie, that can see fresh water (solid blue line) in a nearby tributary. It is interesting to note that because of the height of the river bank Gertie can only see the water on the far side of the tributary. Nonetheless, Gertie is now moving towards the water she can see and will stop and drink as soon as she encounters it.

While working on the AI routines for a dinosaur finding water (see also Dinosaurs, tanks and line of sight algorithms here) I realized that some dinosaurs travel in herds and that where the herd goes is the decision of the leader. Consequently, we will need to have the ability to designate one dinosaur in a group as the leader and the others as followers. Were dinosaur herds matriarchal (led by the senior female, like elephants)? Were dinosaur herds patriarchal (like buffalo)? We just don’t know the answer to these questions but we will be able to explore the possibilities by using Dinosaur Island and observing the results.SmallRule

After posting yesterday’s blog I received an email from my friend, Siobhan, who wrote, “I think dinosaurs are closer to elephants than buffalo, and thus require a matriarch.  Please tell me who I need to pay off and how to see a matriarch implemented! (that’s me subtly casting a vote).

Bribery isn’t necessary. We believe Dinosaur Island should be flexible enough to allow the user to set up any scenario they wish. Today we added the following to the ‘Dinosaur Species’ dialog box:

Just added Herd Leadership variable (Matriarch, Patriarch or Neither in bottom right). Screen capture (click to enlarge).

The just added Herd Leadership variable (Matriarch, Patriarch or Neither in bottom right). Edmontonsosaurus, by default, is now a matriarchal herd. Screen capture (click to enlarge).

Edmontosaurus regalis is now, by default, a matriarchal herd which means that the senior female decides where the herd goes, where it eats, where it drinks, where it rests and how to avoid predators. The default for Tyrannosaurus rex is ‘Neither’ or no herd leadership.



The details of Dinosaur Island.

Just a portion of the data that we are storing about each square meter of Dinosaur Island (screen capture, click to enlarge).

Just a portion of the data that we are storing about each square meter of Dinosaur Island (screen capture, click to enlarge).

The above screen shot shows your just a fraction of the data that we are storing for each of the 4,000,000 square meters of Dinosaur Island. We are tracking the age, health, energy production and weight of every plant on the island. You can also see the data stored for each dinosaur.

It’s important to remember that you, the user, do not need to know any of this information. However the computer model uses this data to ensure that everything that happens on the island is accurate: the plants are growing at the right rate, producing the right amount of energy, dinosaurs are maturing, reproducing, moving and hunting. The more data the more accurate the model.

Also, remember that Dinosaur Island will be in 3D. These are the 2D utilities that are used ‘behind the scenes’ to set everything up.


A Tyrannosaurus rex named Sue.

How the user specifies the creation of a new dinosaur (screen capture).

How the user specifies the creation of a new dinosaur (screen capture). Click to see full-size.

It’s finally that time: we’re adding dinosaurs to Dinosaur Island now. Above is the ‘creation’ screen. As you can see we are modeling each dinosaur in great detail. We are tracking how much they’ve eaten, how much energy they’re expending, what their diet is, age, health. You can even give each dinosaur a personal name.

By the way, none of this is necessary for you to enjoy Dinosaur Island. This is just a glimpse of the ‘behind the scene’ details that we are implementing to assure historical accuracy.

Trivia question: do you know why this T. rex is named Sue? See here for the answer.