Dinosaurs, tanks and line of sight algorithms

A screen capture of MATE (Machine Analysis of Tactical Environments). Note the blue armor unit (labeled ‘0’) just left of the center of the screen. Click to enlarge.

MATE screen capture showing the calculated line of sight of Armor Unit 0 (click to enlarge).

Adjusting the height of an object in MATE to calculate its line of sight.

My doctoral research involved ‘computational military reasoning’¹, a phrase that I coined that means, “computers making tactical combat decisions.” My research was supported in part by DARPA (Defense Advanced Research Projects Agency, the people that really invented the internet). I was able to demonstrate in my MATE (Machine Analysis of Tactical Environments) program that a computer could make what computer scientist John Laird, called, “Human-Level” decisions and could do so very rapidly (see here for more information about MATE). Indeed, my friend, retired Lieutenant Colonel Mike Robel, once said that a computer Course of Action (COA) program like MATE was vitally important because “it’s hard to make your best decision when someone is trying to kill you.”

When I first began working on the design of Dinosaur Island I joked with some colleagues that the AI (Artificial Intelligence) wouldn’t be too difficult as I would just use my MATE program and cross out ‘tank’ and insert ‘triceratops’. There is some truth to that, as we will see today.

One of the first AI routines that I’m adding to Dinosaur Island enables the dinosaurs to find food and water. How does a dinosaur do this? Well, there are actually three ways that a dinosaur finds food and water:

1. The dinosaur looks around for food or water.
2. The dinosaur smells food or water.
3. The dinosaur remembers where it last found food or water.

Right now we’re interested in the first option: looking around (this will also come in handy for spotting predators, too). How does a computer dinosaur ‘look around’?

Luckily, I’ve already solved this problem some years ago in grad school with TIGER (the predecessor of MATE). The solution is a 3D Bresenham line algorithm (I’m not going to write out the algorithm because you can see it here). The Bresenham line algorithm was invented by Jack Bresenham in 1962 when he was working at IBM and it was originally used for controlling a pen plotter (a type of printer that would pick up colored pens with a mechanical arm and draw on rolls of paper). However, if we have a 3D landscape (and we do in Dinosaur Island), we can take Bresenham’s two dimensional algorithm and extrapolate it into three dimensional space to determine if the terrain blocks an object’s view in a particular direction. If we do this in all 360 degrees and plot what can be seen (and what is obscured) we’ll have an image like the second screen shot, above.

Now, in MATE, I had to add a little dialog box so the user could input the height of the observer (the third screen shot showing the height of a tank). But in Dinosaur Island I realized that not only the height of every dinosaur can be calculated (just like the length and weight) but that taller dinosaurs, like the giant sauropods, might have a great advantage because they’ll be able to see farther. This will help them find food and water and see predators before the predators can see them.

Next, I’ll work on the ‘smell algorithm’ which will involve wind direction and speed. Luckily, I solved that problem a long time ago with a game/simulation I did in 1989 called, “UMS II: Nations at War.”

1) My doctoral thesis, “TIGER: An Unsupervised Machine Learning Tactical inference Generator,” can be download here. TIGER was an earlier version of MATE.

5 thoughts on “Dinosaurs, tanks and line of sight algorithms”

1. The dinosaur remembers where it last found food or water? im very interested in how that type of thing could go latter on down the truck when it comes to breeding. will giant sauropods herds be able to remember where they where born? and if so would the hard go back there when its there turn to lay eggs?.

• Yes, I think dinosaurs remember where they last found food. I’m not sure about if they remember nesting sites, or not. However, paleontologist Jack Horner has shown that some species had large nesting colonies.