# 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). 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 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.

• 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.

# The currency of Dinosaur Island.

How the user can set the energy value of a specific plant. (Screen capture from Dinosaur Island)

In England the currency of the realm is pounds sterling. In Russia it’s rubles. A lot of countries have dollars or pesos. However, the currency of Dinosaur Island is energy. Energy is what makes everything happen on the island.

As we saw earlier in What’s for dinner? there is a food chain on Dinosaur Island; and the plants are at the bottom. How much energy does a kilogram of the Nipa fern produce? In, “Sauropod Feeding and Digestive Physiology,” (Hummel and Clauss), a range of values are presented with a low of 4.7 MJ/KG (Mega Joules per Kilogram) and a high of 11.7 MJ/KG (for more information about Joules see here). The screen capture, above, is a close-up of the area where the user can adjust this value for the Nipa fern plant.

So, energy on Dinosaur Island begins with the lowly plants. What happens next?

What does your dinosaur eat? How much energy does he need? How much energy is produced when he is eaten? (Screen capture)

The plants get eaten by a dinosaur, of course. But which plants get eaten by what dinosaurs? Take a look at the screen capture from Dinosaur Island, above. Here you can select what plants each dinosaur can eat. Yes, you can also make a dinosaur either a Meat Hunter or a Meat Scavenger, too. Does that mean you could make zombie dinosaurs like a meat-eating Edmontosaurus regalis? Yes, it does, but that would be just silly.

Obviously, this ability to make a dinosaur a Meat Hunter (Predator) or a Meat Scavenger will come in very handy when paleontologists would like to test their theories about Tyrannosaurus rex as scavenger or a predator.

Users can also adjust some other very important variables for each type of dinosaur. How fast does this type of dinosaur grow? How many MJ/KG does this dinosaur need to eat everyday to survive? How much energy does this dinosaur provide when it is eaten by another dinosaur? How old does this dinosaur have to be to reproduce? And what is this dinosaur’s lifespan (assuming, of course, it doesn’t become dinner for another dinosaur)? By the way, I just read in Islands in the Cosmos: The Evolution of Life on Land by Dale Russell that, “a sample of horned dinosaur population is estimated to have sexually matured at an age of 20 and lived to an average age of 22 years, with a few exceptional individuals surviving to ~80 years.” And that is exactly why we allow the user to ‘get under the hood’ and make adjustments to these values. I’m not an expert paleontologist. I’m a computer scientist that has made a lot of models and simulations and I discovered the best thing for me to do is make available the tools that the experts can use to make the model accurate.

Update: it was announced today (July 16, 2013) that, David Burnham, preparator of vertebrate paleontology at the Biodiversity Institute at the University of Kansas. “has unearthed “smoking gun” physical proof that T. rex was indeed a predator, hunter and killer. In the Hell Creek Formation of South Dakota, Burnham and colleagues discovered the crown of a T. rex tooth lodged in the fossilized spine of a plant-eating hadrosaur that seems to have survived the attack. The team describes the find in the current issue of the Proceedings of the National Academy of Sciences.” Link to the fascinating article here.

# What’s for dinner?

Abydosaurus having breakfast. (This was found on the internet without a credit; if this is your image, please let us know)

For the last week I have been busy researching the details of the food chain of the first inhabitants on Dinosaur Island: Tyrannosaurus rex, Edmontosaurus regalisNipa and Araucaria. The papers that I have been reading are: “Could Tyrannosaurus rex have been a scavenger rather than a predator? An energetics approach,” Ruxton and Houston, The Royal Society, February 2003; “Giants on the landscape: modeling the abundance of megaherbivorous dinosaurs of the Morrison Foundation (Late Jurassic, western USA),” Farlow, Caroian and Foster, Historical Biology, Vol. 22, No. 4, December 2013, pp. 403-429 and “Sauropod Feeding and Digestive Physiology, Hummel and Clauss, Biology of the Sauropod Dinosaurs”, Indiana University Press, 2011 pp. 11-33.

The first food chain on Dinosaur Island is illustrated below:

The T. rex, Edmontosaurus regalis, Nipa and Araucaria food chain. How much energy does the Edmontosaurus receive from eating one Nipa plant? How much energy does the T. rex receive from eating one Edmontosaurus?

What we are trying to ascertain is exactly how much energy is transferred each step of the way. How much energy does the Edmontosaurus receive from eating one Nipa plant? How much energy does the T. rex receive from eating one Edmontosaurus?

For example, in Sauropod Feeding and Digestive Physiology we learn that Araucariaceae is estimated by one source to produce 7.0 Mega Joules per kilogram of dry matter but by another source as between 6.3 and 10.8 Mega Joule per kilogram of dry matter. In Giants on the landscape: modeling the abundance of megaherbivorous dinosaurs of the Morrison Foundation one model is that the estimated energy consumption for a megaherbivore is  55 kilo Joules over kilograms of body mass0.75 per day and another model is for 550 kilo Joules over kilograms of body mass0.75 per day. In Was Tyrannosaurus rex a scavenger? there are also estimates for the energy produced per kilogram of carrion and the amount of energy needed by T. rex if it was a scavenger (slow moving) or a hunter (very fast moving).

As I’ve said before: I’m a computer scientist, not a paleontologist and right now I feel like I’m back in grad school just trying to keep up with my first year classes.  However, I have no doubt that Dinosaur Island will be a very useful tool for answering some of the questions raised in these papers.