Copyright © 2003 by Gene Michael Stover. All rights reserved. Permission to copy, store, & view this document unmodified & in its entirety is granted.
This document can accurately be described as an ``unordered collection Gene's thoughts about an a-life program as he writes it''. It may be badly composed, inaccurate, & rambling.
It's not even hardly nearly ready to show to other people, much less finished. So you download at your own risk, & there are no installation instructions at this time. This will change in the future - but not necessarily the near future.
Before you install Critters, your computer will need:
Critters can be downloaded as a *.cpio.bz2 or a *.tar.gz. Both archives contain the same information; they are just different formats. The *.cpio.bz2 file is smaller than the *.tar.gz file. Anyway, download either of these two archives:
I decided to call my a-life program Critters, with a humorous tip of the hat to the guy who wrote Creatures but also with a disclaimer that it's not a Creatures immitation. It's not even inspired by Creatures. I just got some implementation ideas from the book about Creatures.
At the graphical worst case, I might draw the critters as spheres with color, size, luminosity, or texture map indicating attributes about the critters. So don't get too excited about what it'll look like. Then again, I picture them as sort of semi-metalic cat-like fuzzy things (like a bionic Leopold). Maybe I'll be able to draw them like that.
Originally, I wasn't going to allow for fighting, but this morning, I started thinking about how they could evolve weapons & defenses. It might be neat to let a world evolve where monsters (littler, virtual, bionic Leopolds) evolve to beat-up each other over food or terrirority. It'd be like, I guess, Digimon world without a player.
Maybe I could turn it into a game just by letting a human operator design an avatar that he guides around the world while he beats-up others. Maybe he could try to create & preserve a social order. The idea would be to let the world run all the time on your computer (though you could shut it down). When you wanted to play, you created your avatar & wandered around the world. Maybe you could make your avatar be anything you wanted, whether that was ultra-powerful with infinite health, a tiny scurrying thing, or a copy of whatever was most prominent on the landscape at the time. You could guide your avatar around the world to explore places or see what it would be like to live there. Since you would be a god to the world, the character really would be an avatar.
There would never be a game-over. If the avatar got killed, the program would keep running. You could make another one & explore the world again if you wanted. Maybe you could un-posses an avatar & leave him to the whims of artificial life & evolution.
Initially, I'll probably go with my original idea of no fighting. A slap or a punch here or there, but nothing lethal.
If I want to have combat in the hopes of evolving virtual, miniature fighting terrors, I could defined some elements (earth, air, fire, water, nukelear, cold, electricity, ...). Besides elements, there might be attack modes such as slice, hit, pierce, pressure, vacuum, & others. And I guess an attack might be immediate or ranged.
For defenses, the DNA could contain a list of genes that defend against an element. Maybe each gene against some element removes one percent of the damage an attack of that element would do. So to block all the damage from nukelear attacks, a critter would need 100 nukelear defense genes. There could be defense genes for every element, every mode, ranged, & immediate. The length of the list could evolve, too. I might make it small, like 100, but maybe evolution would lengthen (or shorten) it. Maybe I wouldn't have a limit on it.
There could also be weapons. Each weapon would have an element, a type, a mode, a reload time, & an effeciency. Reload time dictates how often it can be used. Efficiency determines how many calories are required to use it & how much damage it does.
Using a weapon would consume calories. I don't think I'd go to the trouble of implementing hit points. Instead, a weapon might disable another type of weapon for a time, & being hit with an attack could consume calories. Maybe being hit with a weapon would also affect the drives of a critter. (Hmmm... Maybe each weapon could evolve its own effect, too. It could evolve which drive it affects in the target of the attack. So it'd be possible for a weapon to, say, make another critter happy or lonely or horny or whatever. Some effects might mean that a weapon wasn't a weapon any more. Hmmm...I like that idea. It'd be cool to see if maybe some race developed a horny gun & explicitly had no defense to it. Maybe there would be more clever things that could evolve.) As with the non-combat version of the program, a critter dies if its glycogen level reaches zero.
(Using the term ``game'' loosely.)
There is a 4-dimensional universe. It has three linear dimensions: depth, width, & height. It has one time dimension.
The linear dimensions are measured in millimeters.
Time in the game is measured in ``ticks'', which are about equivalent to one centisecond in the real world. The game universe's time continuum is connected to our time continuum in that both have the same idea of a forward direction & the game's time exists within our time (starts after ours started, ends before it ends), but the two time continua do not advance at the same pace. So I chose to use a new term, ``tick'', for the game's unit of time to avoid confusion. Otherwise, I would have said ``game seconds'' and ``real seconds'' too often.
The game's linear dimensions do not intersect our own, so there should be no confusion if I use the same terms in the game that we use for our real linear dimensions.
The game universe contains one world. The world is a cube, one kilometer on each side. Its axes are named x, y, & z. For any axis, the minimum value is 0, & the maximum value is 9,999,999. Values outside of those ranges put an object outside of the world & outside of the game.
The x & y axes are width & breadth, but which is which depends on where you are when you ask.
The z axis is height. The ground is where z is 0.
The simple viewer program is phylis/bin/viewer. The graphical viewer program is written in C. It uses GLUT (which uses OpenGL). The sources are many *.c files in phylis/src/. It reads descriptions of the world from standard input. The description of the world is just a list of objects, their types, sizes, locations, orientations, & colors. Then it displays them. It does this continually until end-of-file.
The types of objects it can draw are hard-coded. They are classes effectively, though I didn't use C++. Each class has a name, which is a string & must be the same as the name for the class in the Lisp server.
A later version will connect to the simulator with a network socket instead of relying on standard input. It might also allow the user to control an avatar in the simulated world.
The reasons for putting the display in a program separate from the simulation are in Figure 7.1.
I'd like to call a function to produce a world. The function could produce the world in a lot of ways. Maybe it constructs a new world, but I've learned already that creating a new world in code is difficult. To create a world with complexity & richness, you probably need a graphical world editor. Maybe there is a function which invokes a fully graphical & interactive world editor. Or maybe there is a function that loads & returns a world from a file or other data store. However it's done, whether by calling make-world, edit-world, load-world, or some other function, let's say for now that I have a function which returns a world. I'd like to do something like this:
(defvar *world* (make-world ...))
A world contains all the objects in it & an event queue.
I'd like to hand that world to a loop that continually updates the world & everything in it until it's time to quit. The loop will need a function that tells when to exit & a function to call whenever there are no events in the queue that are ready to execute. For now, assume that I have a function called done-p which returns true if & only if it is time to exit the loop. Also assume I have a function called idle which is to be called whenever there are no events to execute. What happens inside idle? More on that later.
The loop should probably return the world itself.
I'd like to use that loop like this:
(setq *world* (run *world* #'done-p #'idle))
Originally, I wanted Critters to run in its own time continuum in the hopes that it would run faster than real-time. Experiments have shown that on the old hardware I plan to run it initially, there is no way it will run faster than real time. Heck, it doesn't even run in real time. Also, when watching simulated physics, it seems best if objects move in real time. Otherwise, it's just too confusing. So now I want Critters to run in real-time.
The main loop will need a way to fetch the current real
time.
I want to support thirty frames per second, so the
time-fetching function needs a resolution of at least
second. The
get-universal-time function won't work for this purpose because it supports
resolutions of whole seconds. I guess the
get-internal-real-time function is what we need, but it measures time in
internal-time-units-per-second,
& converting that to seconds might be error-prone.
So we'll make our own function to return the real time in
high-resolution. It returns the real time in seconds, but
with a resolution that's hopefully at least second. Here is that function:
(defun now () \\ (/ (get-internal-real-time) internal-time-units-per-second))
That's one possible implementation, I hope. Yet another reason for putting inside a function of its own is to make it easy to change the implementation without changing the loop that uses it.
I've run that function in clisp to test it, & I see that the numbers it returns are big. It returns rationals, but if you convert them to floats, you lose important digits in the mantissa. In clisp & some other Lisps, I presume the system won't lose precision as long as I don't tell it to convert to a float, but some Lisps might not have enough precision (maybe because they automatically convert to a float). If that ever proves to be a problem, I might reduce the number of significant figures that are required by returning the high-resolution real-time since the program started. The now function in that case would resemble the one I've written here, but it would need to know the time at which the program started.
Here's the loop that uses the now function, the world, a done-p function, & an idle function, the way I've just described them.
(defun default-run-idle-function ()
"This is the default IDLER function. More about
its implementation later."
...)
(defun time-to-next (flez)
"Return the number of seconds from now until the next event in
FLEZ is ready to execute. Returns 0 if the next event is ready
now or is over due. Never returns a negative number."
(max 0 (- (flez-next-when flez) (now))))
(defun run (world done-fn &optional (idle-fn #'default-run-idle-function))
(do ()
;; See if we're done. Return the WORLD if we are.
((funcall done-fn) world)
;; Let the IDLE function run. Tell it when the next
;; event is scheduled. The idler function might
;; return immediately, return exactly when the next function
;; is to execute, or return at some time in between. If
;; it's being a sloppy & disobedient function, it might
;; not return until after the next event is due. Heck, if
;; it's a very clever function, it might return before we
;; call it.
(funcall idle-fn (flez-next-when (world-flez world)))
;; Execute whatever events are ready to go now.
(flez-tick (world-flez world) (now))))
Notice how little the run function knows of time. It doesn't know how to compare times or do math on them. It only knows how to obtain the current time, with the now function. If we wanted to remove even more knowledge of time from the run function, we could replace the now function call with a functional argument which would be the function for obtaining the current time.
Enough explanation. Here's the run2 function which knows even less of time than does the run function.
(defun run2 (world done-fn now-fn &optional
(idle-fn #'default-run-idle-function))
(do ()
;; See if we're done. Return the WORLD if we are.
((funcall done-fn) world)
;; Let the IDLE function run. Tell it when the next
;; event is scheduled. The idler function might
;; return immediately, return exactly when the next function
;; is to execute, or return at some time in between. If
;; it's being a sloppy & disobedient function, it might
;; not return until after the next event is due. Heck, if
;; it's a very clever function, it might return before we
;; call it.
(funcall idle-fn (flez-next-when (world-flez world)))
;; Execute whatever events are ready to go now.
(flez-tick (world-flez world) (funcall now-fn))))
It's a nice idea, but I think I'll use the run function. Even though it has more knowledge of time, it doesn't have too much.
The done-fn returns true when it's time to exit the loop. It could use whatever criteria the caller wants to determine when it's time. It could let the program run for a fixed amount of real time or a fixed number of iterations through the loop. It might wait until some state has been reached in the world.
The easiest done-function might rely on other functions or events from the queue to set a global variable. So that done-function would be like this:
(defvar *done-flag* nil "Set this when it's time to exit the main loop.") (defun donep () *done-flag*)
So how about that default-run-idle-function? What does it do? A simple one would return immediately. Then the loop would continuously check the Flez queue until an event was due to execute. It would execute that event & then run through the loop again, including calling the idler function each time.
The problem with an idler that returns immediately is that it creates a busy loop that consumes lots of CPU cycles.
If the idler sleeps until the next event is due, you save CPU cycles. So the default idler function should sleep until the next event is due to execute. How does it know when the next event is due? From its single argument, which is the time for which the next event is scheduled.
Here's one possible cycle-saving idler function:
(defun simple-idler (when) "Sleep until the current time is WHEN. Assume that WHEN is a time expressed in seconds with the same bias used by the NOW function. Return no useful value." ;; We use the SLEEP function, which is in the Common ;; Lisp library, but I'm not sure it's guarranteed ;; to work with fractions of seconds. So this might ;; not actually be portable. On a Lisp that can't ;; SLEEP for fractions of a second, an implementation- ;; specific alternative might be available. For ;; example, your Lisp might offer an interface to ;; unix's SELECT system call. (sleep (- when (now))) 'simple-idler)
If the game needs to respond to external events, the place to check for them is in the idler function. My Lisp server for Critters will allow multiple network connections from client viewer programs, & in the distant future, it might allow commands from the client viewers. The place to check the client connections for input or for space in their output queues is in the idler function. I don't yet know the data I'll be able to give my idler function, but here is an example idler function that checks a socket for input or output & concerves CPU cycles by sleeping. It uses clisp's socket:socket-status function, which is non-portable.
(defun seconds (dt)
"Return the integral number of seconds from DT."
(multiple-value-bind
(sec usec) (floor dt)
(declare (ignore usec))
sec))
(defun microseconds (dt)
"Return the integral number of microseconds from DT."
(multiple-value-bind
(sec usec) (floor dt)
(declare (ignore sec))
(* 1000 usec)))
(defvar *the-socket* (initialized-to-whatever))
(defun socket1-idler (when)
"CPU cycle-saver that assumes one socket for external
events."
;; For SOCKET:SOCKET-STATUS, we must specify integral
;; numbers of seconds & microseconds. Notice that we
;; also ensure that the duration is non-negative.
(let* ((dt (max (- when (now)) 0)))
(case (socket:socket-status *the-socket* (seconds dt)
(microseconds dt))
(:input (read-the-socket))
(:output (write-the-socket))
(:io (read-the-socket) (write-the-socket))))
'socket-idler)
That idler function assumes we have just one socket. In practice, the program will have a server socket & lots of client connections, so I'll need a more general idler function.
For the more general idler function, I could keep a list of the sockets in a global variable, *sockets*. Each element in the list could contain the socket, the reader function for it, the writer function for it, & the operation we want (:input, :output, or :io). Each of those elements could be a structure, but they are short enough that I'll probably make them lists. The elements in those lists are positional because there aren't many. If there were a lot, I could make them assoc lists, but if there were a lot, I would make them structures, anyway.
To avoid polluting the name space, I'll put this socket-related code, including the idler function, in a package of its own. Nevertheless, I will ignore that package magic for now.
Here is the global list of sockets:
(defvar *sockets* () "Global list of sockets")
Of course, we need to put some sockets in it. Here is now to do that, though this sample code is not part of the hypothetical sockets package.
This is example code. It is untested as of 9 December 2003.
Example of how to initialize the *sockets* global list of sockets. For a server process, you probably want to initialize the list with a server socket. Here's how, using clisp's socket functions.
(defvar *tcpmux-port* 1 "TCP port number for the tcpmux service")
Create a server socket for tcpmux & put it on the global list of sockets. The server socket has a reader function, no writer function, & its state is :input.
(push (list (socket:socket-server *tcpmux-port*)
:input
#'tcpmux-server-reader
nil)
*sockets*)
Now to implement tcpmux-server-reader. The multi-socket idler function calls it whenever the server socket is ready to read. When a server socket is ready to read, it means a connection is pending. When we call accept on the server socket, we get a new client socket. We'll need to put it in the global list of sockets with the proper reader & writer functions & the proper state.
Here is a reader function for a tcpmux server socket.
(defun tcpmux-reader (s)
"Do a read operation on a tcpmux client socket.
I guess it needs to read a service type name &
connect the socket S to a function that handles
that type of service, but let's just ignore all
that for now."
(whatever goes here doesnt matter))
(defun tcpmux-writer (s)
"Same comment as for tcpmux-reader."
(ya ya ya))
(defun tcpmux-server-reader (s)
"Accept a new tcpmux connection & insert it
into the global list of sockets."
(server-reader s #'tcpmux-reader #'tcpmux-writer
:io))
In proper Lisp fashion, this new function does very little & delegates the real work to another function. Here's an implementation of that other function, server-reader.
(defun server-reader (s reader-fn writer-fn state)
"Given reader & writer functions for a client, & a
state which must be :input, :output, or :io, accept a
new client socket & add it to the global list of
sockets."
(push (list (socket:socket-accept s) state
reader-fn writer-fn))
'server-reader)
Stopped here. Need to implement the following, multi-socket idler function. It's body right now is a copy of the single-socket idler function. Can't have that. Stopped here!!!
(defun socketx-idler (when)
"CPU cycle-saver that assumes one socket for external
events."
;; For SOCKET:SOCKET-STATUS, we must specify integral
;; numbers of seconds & microseconds. Notice that we
;; also ensure that the duration is non-negative.
(let* ((dt (max (- when (now)) 0)))
(case (socket:socket-status *the-socket* (seconds dt)
(microseconds dt))
(:input (read-the-socket))
(:output (write-the-socket))
(:io (read-the-socket) (write-the-socket))))
'socket-idler)
While my Critters Lisp server is running, I plan to give it commands in command files. It will periodically check for a command file. If the file exists, the server will read & eval the Lisp expressions in it, then delete the file.
Here is an implementation of the command function. It should be scheduled in the event queue about every five seconds.
(defun check-command-file (fz when)
(declare (ignore fz when))
(let ((pn (make-pathname :name "critters" :type "com"
:version :latest))
(delete-p nil))
(with-open-file (strm pn :direction :input
:if-does-not-exist nil)
(when strm
(mapc #'eval (read strm))
(setq delete-p t))
(when delete-p
(remove-file pn))))
'check-command-file)
The check-command-file I've shown here always looks for a command file named critters.com. If the file exists, the function assumes it contains one list of Lisp forms. The function reads the list & calls eval on each form in it.
This example function also deletes the command file so it won't be executed again. On unix, it would be fine to delete the file even while it's open, but that might not be true on other operating systems. It is also possible that a Lisp implementation on unix would artificially prevent deleting a file that is open. For all these reasons, the function deletes the file after it has read & closed the file.
To stop the Critters server if I use the done-function that checks the global variable, I'd create a command file that sets the done flag to true. From the unix command line, I'd do this to stop Critters:
$ echo \(\(setq *done-flag* t\)\) >command.tmp $ mv command.tmp critters.com
In practice, it would probably be okay for the echo to write to the critters.com file directly, but in theory it would not be safe. It is better to write to a temporary file & then rename. On unix, renaming a file uses two link operations, & links are created & destroyed atomically. So the mv is safe.
Make a world. It creates the Critters & schedulers their advance events.
Schedule a display event. Schedule a check-for-command-file event.
Create a server socket & schedule an event for it. No, no. Put it in the list of sockets the idler checks.
Call the run loop.
To be continued ...
The notes in this chapter are transient. Place immutable notes in the Log.
To start the environment for programming, debugging, & testing, do these things on a terminal:
To run all the test programs, evaluate ``(check *tests*)''. (You can also run those test programs & others from the Unix command line: ``make check''.)
On another terminal, run emacs & open /home/gene/src/critters with it. The Lisp sources are in the src/ directory.
There are test programs that can be run from the command line. cd into $HOME/src/critters/. The programs are in ./bin/, but some programs in that directory are not the test & demo programs.
A ``world'' is a simulation. It contains the Critters, other entities, terrain, bookkeeping, statistics, & nearly all other attributes of the simulation. It doesn't contain the stopping condition or the display.
How to implement the type world?
I could make it a structure, but since few functions operate on worlds, & since I'd like to try the technique I discovered of using apply on a function & a list to split the list into members, treating it as a structure8.1, I'll use a list.
So a world is a list. It'll have these elements:8.2
Each function that operates on a world has arguments that correspond to the elements of a world. Each of those functions returns a new world, a list assembled from new elements & whatever old elements were unchanged. So if function fn operates on a world, & if world is bound to a world, then the way to call fn is:
(setq world (apply #'fn world))
function
run world done-fn
This function should have a different name.
Advances the simulated world until ``funcall done-fn'' returns true. Returns the new world. Probably modifies world, but you should use the result, anyway.
done-fn must be a function, never nil.
> (defun create-world (...)
"Create a world from scratch \& return it."
...)
CREATE-WORLD
> (defun make-timed-done-fn (minutes)
"Return a function which returns true
MINUTES after it's created."
...)
MAKE-TIMED-DONE-FN
> (progn
(setq world
(run (create-world ...)
(make-timed-done-fn 10)))
; Use the PROGN so the read-eval-print loop won't
; print the world. (It could be big.)
nil)
NIL
After evaluating those forms, the symbol WORLD will be bound to the new world. The world will have been created & then run through the simulator for ten minutes.
run also accumulates the real-time & game-time data members of the world.
I guess a possible implementation (untested at this point) of run would be:
(defun run (world done-fn)
(do ((start-time (get-universal-time)))
((funcall done-fn)
(progn (incf (world-realtime world)
(- (get-universal-time) start-time))
(setf (world-gametime world)
(flez-next-when (world-queue world)))
world))
(
function
step oblst realtime gametime
ball00 drops a wire-frame sphere over a grid. Does some simple gravity-only physics, so the ball accelerates as if it were falling. (It is falling in that world.) The source for the command line program is src/ball00.sh; for the Lisp, src/ball00.lisp.
The viewer program is bin/ball00viewer, the source is src/ball00viewer.c.
The forms in src/ball00.lisp are probably incompatible with other apps.
See the notes for 11 June 2003 in the Log.
Installed Mesa 5.0.1 on Plague. Was a painful process because ``make check'' doesn't work on my distro & some others10.1 & because of some unfortunate little mishaps in my test programs. Wouldn't have gotten it working without the help of Tom Williams (tomdkat).
I had planned to connect to OpenGL with C, to implement the simulation & logic part of the program in Lisp, & to have them in the same program via clisp's foreign function interface, which I have never used. Concluded that it'd be simpler to separate them into two programs with a simple protocol for communication.
Today, I implemented an early version of the C program. Called it viewer00. It draws spheres that move around. You can specify the eye & the point it is looking at; both the eye & the point wander around the world. When connected to the simulation, Lisp will tell the C program where the objects are, their type (so C knows how to draw them), & their velocities.
On both Plague & Palsy, it gets about 5 frames per second with hundreds of spheres moving. It might be able to go faster. I don't know because the program only requests 5 fps so far. I was impressed with how easy it was to achieve 5 fps & how good it looks, though I know it isn't nearly as good-looking as 30+ fps.
Began writing the first simulation part. Didn't get very far. Called it critters00.
I've been thinking about data structures for terrain. Woah, terrain ain't easy.
The simulation part could probably work with a matrix that held the terrain type & elevation for each cell in the world, but the graphics part can't use that. The graphics part needs polygons to draw.
Given the first, you could generate the second. That's a brute-force way of making an appropriate data structure, & I'd like to think about more elegant solutions.
Originally, Critters were going to walk on land, but as I experimented with 3-D graphics over the weekend, I decided to make them swim in a 3-D world because it'd look kind of cool if the camera wandered through schools of them. You could see Critters above & below the camera.
I thought about it again yesterday. For the user (a human) to feel more empathy towards the Critters, they should walk on land. In other words, they can be cuter & more easily likeable, less alien, if they walk on land.
I'd still like to make use of a 3-D world. I could do that by allowing Critters to jump, like cats. I could make use of 3-D terrain, maybe even have floating platforms or castles. Critters could jump onto higher or lower platforms. Might want to make the cost of a jump be higher than the cost of walking the same distance.10.2 So Critters are kind of like cats.
It might be useful to decide on units of measurement, give Critters & their world sizes that I can visualize. If I can visualize them, it might be easier to keep their world consistent. I suspect it'll be more fun to write.
How about I measure linear dimensions in their world in centimeters? The limit of resolution on the map is one centimeter. A Critter is spheroid, about 5 centimeters in radius. Future versions of the program can give Critters a more complex shape, but spheres are easier, & they will work fine for now.
So a Critter is smaller than a house cat, but its volume is in the same scale. Like a cat, maybe a Critter can jump upwards about 200 centimeters. For grins, let's say a fall over 200 centimeters will hurt a Critter, but he can jump down that distance or fall less distance without being hurt.
The minimum radius of an object can be zero, but I'll allow only whole numbers, so the smallest non-point object will have a radius of 1 centimeter. That'll be the plants & fruits that Critters eat.
I've already decided that the world is 30,000 by 30,000 by 30,000. If each dimension is in centimeters, their world is 300 meters by 300 meters by 300 meters. I hope that's big enough.
Created a display protocol & two classes to implement it: basic-display & text-display. I sketched the generics & their documentation during some free moments at work today. It's amazing how much documentation you write when you don't have a Lisp handy to actually evaluate forms.
Created test.lisp & test9900.sh. Did a few tests.
Started twiddling function critters-loop to make it run using a text-display. Besides the ``display'' protocol, I also sketched some functions at work which relate to critters-loop. Don't have time to try them out tonight.
I think I'll implement gravity & other forces as tasks. Each will be a task. The gravity task scans the objects in the world. It accelerates each object towards the ground by adding a downward vector to the object's velocity.
That's the theory, anyway. In practice, it might be a good idea of gravity could tell when an object was already on the ground or otherwise supported, so it's velocity didn't need to change.
Gravity could run about as frequently as a movie frame. Gravity in
the real world is 979 centimeters per second. If gravity runs thirty
times a second, then each time it runs, it adds
in a downward
direction to each object's velocity (except for the objects which are
already on the ground or otherwise can't fall).
Some objects might be exempt from gravity. Maybe ghosts. I don't plan to have ghosts in Critters.
Flying objects, like birds or helium balloons, are not exempt from gravity. I could implement them as immune to gravity, but I think a better way is for the act of flying to accelerate the object upwards. If a helium balloon accelerates upwards at 1,000 centimeters per second, then it will rise.
I guess I could implement wind or ocean currents the same way, one task each. The forces might be smart, knowing to affect only the objects in their path or not to affect objects that are shielded by a building or a wall. The accelerations could also be dependant on the mass of the object. With gravity, that doens't matter much, but it could with wind or currents.
There are other effects which I want to implement the same way. They aren't exactly forces of nature, like gravity is, but the same implementation technique could apply.
One such force that isn't a force is movement. The movement task could scan all objects & odate their positions by their velocities.
Another force task is temperature. It could alter the temperature of objects by moving them slightly in the direction of the ambient temperature.
Is the order in which the forces execute important? Sure it will effect the exact results, but if they all execute at about the same frequency, & if the frequency is high, will it change the overall results?
I'd like to think that the exact ordering of the forces isn't important. I'd like to think that, when a function initializes the event queue, it can insert all the tasks that are the forces, & it can give each of those a randomly selected first execution time within the first second of the program. The periods of the tasks would be identical, but their orderings would be random. I'd like to think that, if the only difference between the inputs of two runs of the program was the ordering of the forces, there would be no significant difference in the output.
To help test this, maybe I should provide the program with more than one random number seed. One of those random number generator seeds would be specifically for shufflling the tasks that are the forces.
There's no reason critters must live in a three-dimensional world. What types of critters would evolve if they lived in a world of more dimensions?
I'm at a sort of empass. Need to connect the skeletal graphics display to the simulation. Also need to separate the simulation into a generic part & an application-specific part. It should be easy to load the simulation, create a display object, & then tell them to operate on an application-specific world.
Anyway, seems that the easiest way to deal with all this is to write a simple simulation. I think a bouncing ball is a good idea. I'll try to make it general enough that you can plugin the number of bouncing balls you want. Ideally, the fall-out of writing a bouncing ball simulation will be a display & a generic part of the simulator that work. Then I can plugin the critters. Finally!
The ball viewer gets 5 fps using Plague as an X-term & running running BALL00 on Palsy, a 400 MHz Gnu/Linux machine at the other end of my apartment.
On Plague, which is a Sony PCG-XG500 laptop with a 700 MHz CPU & god knows what video hardware, it gets over 33 fps at 33 percent CPU usage & wihout busy-waiting. By cranking down the timer interval on glutTimerFunc to 1, it looks like it peaks at 93 fps which surprises me because most of the books I've been reading say that you need to do OpenGL in hardware to reach 30 fps without pulling busy-wait tricks.
(Oh, & this is with some hard-coded objects, with the viewer program temporarily disconnected from the simulator. It looks like the bottleneck is the communication between the two programs, so for a production-quality frame rate, it may be necessary to link the graphics parts with the logic parts. I'm going to see how far I can go while keeping them as separate programs.)
I have writer's block. To help me work through it, here are some thoughts, stream of consciousness style.
I'm having trouble writing the simulation of basic physics properties. So here is an attempt to work through the problems.
I'd like to put things in a world, set their states, & tell the engine to run through them until I tell it to stop.
So I guess that implies a World object to contain the Things & the event queue.
(defclass World
((things :accessor things
:initarg things
:documentation "List of all things in the World.")
(flez :accessor flez
:initform (create-flez)
:documentation ``The event queue'')
(is-done :accessor is-done
:initform nil
:documentation ``flag to tell event loop when to stop'')
...
..
.)
(defmethod run ((self world))
(setf (is-done self) nil)
(until (or (is-done self) (flez-is-empty (flez self)))
(wait self)
(flez-tick (flez self))))
Do you see the ``(wait self)''? That gives the World an opportunity to wait for real time to catch-up with simulation time. For a simulation, with should run as fast as it can, independently of real time, the wait method shouldn't do anything. A simulation's wait method should be like this:
(defclass simulation (world) ...) (defmethod wait ((self simulation)) ;; Do nothing self)
For a game, which runs in real time, it should be like this:
(defclass game (world) ...) (defmethod wait ((self game)) (sleep (/ (flez-next-when (flez self) 1000.0))) self)
This Game's wait method assumes that hte queue uses milliseconds. I don't at this time know how cleanly that assumption can be removed. That doesn't matter now because I will track time in milliseconds & because I'm writing a simulation, not a game.
An interactive game would also want to check for user input in its wait method. Maybe it's not a ``wait'' method. Maybe it's a ``tick'' method or an ``iteration'' method. It isn't all that important, actually, because you could achieve virtually the same goals by scheduling a task to check for user input.
A World doesn't do much. It could be a structure or even disconnected list of things, an event queue, & a done flag. A World is not necessary, but I think it'll be a convenient way to keep things & their event queue together.
Programming a World is a matter of implementing the classes of the things, creating things, initializing them, & putting them in the world, & of initializing the event queue. I could do that with functions or by loaidng from a file.
Oh damn. I forgot that a world needs a display. Or does it? I guess a display could be a Thing. Or a display could be outside of the World. The World could have a display member, or the display could be updated as a task.
I'll let class World remain ignorant of displays. Subclasses can use displays, or displays can be in the tasks. For now, tasks will be adequate.
Back to iniitalizing a World.
Let's ay I want a bouncing ball simulation. I could write a function to create & initialize such a world.
(defun make-ball-world ()
(let ((w (make-instance 'world))
(ball
(make-instance 'ball
:x 15000 :y 15000 :z 30000)))
(push ball (things w))
(flez-task (flez w)
#'(lambda (fz when)
(mapc #'(lambda (thing) (movement thing))
(things w)))
3 100 'movement-task)
(flez-task (flez w)
#'(lambda (fz when)
(mapc #'(lambda (thing) (gravity thing))
(things w)))
1 100 'gravity-task)
(flez-task (flez w)
#'(lambda (fz w)
(mapc #'(lambda (thing)
(display:pos *display*
(x thing)
(y thing)
(z thing)))
(things w))
(display:elapsed-time
*display*
(/ when 1000.0)
(- (get-universal-time) last-time))
(setq last-time (get-universal-time)))
2 100 'display-task)
w))
Notes about that function:
(world:run (make-ball-world))
With these items in mind, let's rewrite:
(defun make-physics-task (world)
#'(lambda (flez when)
(mapc #'(lambda (thing) (gravity thing when))
(things world))
(mapc #'(lambda (thing) (movement thing when))
(things world))))
(defun make-display-task (display world)
#'(lambda (flez when)
(mapc #'(lambda (thing)
(display:pos display
(x thing) (y thing) (z thing)))
(things world))
(display:elapsed-time display
(/ whyen 1000.0)
(- (get-universal-time)
(start-time world)))))
(defun command-task (flez when)
;; Check for a command file. If it exists, open it &
;; evaluate everything in it.
)
Hmmm...Maybe the command task should allow the filename as aparameter. That paramter might be be a pathname object. So we get:
(defun make-command task (pn)
#'(lambda (flez when)
(when
(with-open-file (pn :if-does-not-exist nil)
...)
(delete-file pn))))
That's all the tasks we need for bouncing balls. To recap, we have functions to make these tasks:
Moving to tasks to separate functions reduce the size of the make-ballworld function. Now let's rewrite that function:
(defun make-ball-world ()
(let ((w (make-instance 'world))
(ball (make-instance 'ball)))
(push ball (flez w))
(flez-task (flez w)
(make-display-task (make-3d-display) w)
0 100 'display-task)
(flez-task (flez w)
(make-physics-task w)
1 100 'physics-task)
(flez-task (flez w)
(make-command-task "tmp/ball.cmd")
0 7000 'command-task)
w))
If I wrote it correctly, you coudl do this on Lisp's interactive command line:
? (setq w (make-ball-world))
;; Insert an event to quit after 60 seconds
;; of game time. Otherwise, we could go to
;; another command line \& create a file
;; called ``tmp/ball.cmd'' with a command
;; to quit.
? (flez-post (flez w)
#'(lambda (flez when)
(setq (is-done w) when))
:when 60000
:tag 'done-event)
;; Run the simulation for 60 seconds
? (run w)
When run returns, the simulation has run for 60 seconds of game time. The graphics window is still visible, but the ball in it is not moving.
We could run for another minute of game time by inserting another ``done'' event, & evaluating ``(run w)'', or we could forgoe the done event, evalutate ``(run w)'', & place a command in ``tmp/ball.cmd'' when we are tired of watching.
The World should track its own elapsed time, both real & game time. It wouldn't need to update it very frequently. Hmmm...The display update depends on the elapsed time. Should the World update its elapsed time every time through the loop? Maybe it could update game time every iteration, but it could update real time less frequently, like every 10 game seconds, via a task in the event queue which the run method inserts & removes behind the scenes.
How about a ball world with more than one ball, each with randomly generated initial state?
(defun make-n-ball-world (n)
(let ((w (make-instance 'world)))
(do-times (i n)
(push (make-isntance 'ball
:x (random 30000)
:y (random 30000)
:z (random 30000))
(flez w)))
(flez-task (flez w)
(make-display-task
(make-insatnce '3d-display)
w)
0 100 'display-task)
(flez-task (flez w)
(make-physics-task w)
1 100 'physics-task)
(flez-task (flez w)
(make-command-task "tmp/nball.cmd")
0 7000 'command-task)
w))
A Thing is an object in the game. I eman it can be displayed; the user is aware of it. Some objects are not Things. An event in the queu is not a Thing. The World is not a Thing.10.3 A Critter is a Thing. A piece of food for a Critter is a Thing. I guess the ground & walls of the World could be Things.
So let's think about class Thing. A Thing can be the target of the forces & effects that might belong in a physics task, such as gravity, motion, & temperature.
Thought a bird can fly, it's a Thing. Gravity operates on it like other things, but if the bird is in flight, it accelerates upwards, against gravity. The upwards force is independant of gravity.
What about a ghost? It is not affected by gravity. Is it a Thing? I think it is a Thing, but its mass is zero, so it is immune to gravity.
So Things have mass (possibly zero). A low-resolution approximation of mass is to have an ``is affected by gravity'' flag. Or the gravity method for an object could know how to apply gravity to the object.
The protocol for all Things includes:
Things also have accessors for position, velocity, mass, temperature, & maybe others.
We'll need the dimensions of each Thing. In the future, bounding boxes, bouncding spheres, & list of polygons. For now, everything is a sphere, which requires every Thing to have a radius.
We need some kind of collision detection between two Things, maybe like this:
On second thought, collision detection shouldn't be a method of Thing. Why should one Thing & not another detect collisions? What if the algorithm depends on subclasses of Thing? Which class's collision-detection method takes precedent? Also, the collision-detection algorithms I've seen can do some optimizations if they have access to the global list of objects. So collision detection is a task.
Maybe the collision detection task belongs in the physics task. Yes, it is appropriate that collisions are a physical effect like movement (or part of movement). Reaction to collision belongs in Thing & its subclasses.
So the Thing protocol is mostly about reacting to the events in the World. The events we can tell a Thing about currently are
It also has an exists flag which can be fetched or set. A Thing has a radius, colour, mass, & temperature, each of which can be fetched or set.
Now let's make a rubber ball. It can't be eaten, & it moves if you hit it or if it bounces off something. It falls when not on the ground.
Chewed is easy. Being chewed doesn't effect a ball at all. That should probably be the default behaviour for Thing:
(defmethod chewed ((self thing) other) (declare (ignore self other) nil)
Gravity acceleratees a ball downward unless the ball is already on the
ground (
). For generic Things, gravity could accelerate them
downwared when mass is positive. Gravity has no effect when mass is
zero. Might as well have antigravity for negative mass:
(let (
;; gravity acceleration in centimeters per
;; millisecond
(g ...))
(defmethod gravity ((self thing) millisec)
(unless (or (zerop (mass self) (minusp (z self))))
(let* ((basic-acceleration (* g millisec))
(applied-accel (* basic-acceleration
(signum (mass self)))))
(incf (dz self) applied-accel)))
self))
Balls can use the movement from Thing:
(defmethod movement ((self thing) millisec) (incf (x self) (round (* (dx self) millisec))) (incf (y self) (round (* (dy self) millisec))) (incf (z self) (round (* (dz self) millisec))) self)
How about being struck? maybe if the mass of self is less than the mass of the striker, self starts to move. Otherwise, no effect. This could be the behaviour of Thing.
Here some first-thought pseudocode for a collision-detection task:
(defun distance (x y)
"Return the distance from X
to Y. That is, X - Y, as a vector. X & Y are both arrays
that determine a location. They should have the same number
of elements."
(let ((sum 0))
(dotimes (i (length x))
(incf sum (- (aref y i) (aref x i))))
(sqrt sum)))
(defmethod collide? ((self thing) (other thing))
(< (distance (position thing) (position other))
(+ (radius thing) (radius other))))
(defun list-of-collisions (x lst)
"Return list of CONSes. Each CONS has two things which
collide."
(mappend #'(lambda (y)
(if (collide? x y)
(cons x y)
()))
lst))
(defun move-apart (x y)
???)
(defun shuffle-forces (x y)
???)
(defun make-collision-task (world)
#'(lambda (flez when)
(mapcar
#'(lambda (lst_pairs)
(mapcar #'(lambda (pair)
(move-apart (car pair) (cdr pair))
(shuffle-forces (car pair) (cdr pair)))
lst_pairs))
;; Get list of lists of collisions. Each collisions
;; is a CONS.
(maplist #'(lambda (lst)
(list-of-collisions
(first lst) (rest lst)))
(things world)))))
Ug. There's a long way to go, I see. At what points on their surfaces do two object's collide? At what angle? Need to know those things to detlermine how they react. Is there a simple way to approximate it? If you could quickly deterine the axis along which they mostly strongly collided, you could just reverse the direction on that axis alone; that'd be a decent approximation.
I could make a viewer program that was designed to run over slow networks so friends (& me, when I'm not at home) could see the progress of an on-going Critters run.
The client program would make a session with a server at CyberTiggyr.COM. TCP would be best to make it through firewalls, but UDP is so much cooler & probably more appropriate for the application.
The server is a display device. Critters doesn't know about it. Critters just sends update messages to the server, as it does already.
The special display server accepts connections. It expects that the incoming data from Critters requires more bandwidth than the clients have, so instead of letting Critters block while it waits for the server to repeat the last update messages to all the clients, the server always sends whatever will fit in a client's buffer & discards the rest. So it eats data from Critters as fast as possible & over a LAN connection, & it sends what it can to the clients, dropping the rest. It doesn't even ensure that a client receives an entire message. The server sends the bytes that it can & drops whatever it can't.
It's easy to see that UDP would be perfect for this, but UDP doesn't go through most firewalls (including CyberTiggyr's), so I need a TCP option.
The client/viewer programs slurp-up whatever data they get from the server. They scan for a beginning-of-record, discarding data until they find one. Then they collect data until they find an end-of-record (or another beginning-of-record, in which case they discard the incomplete, buffered record). Then they parse the record, keeping in mind that the record might be garbled. When they get a good decode, they update their internal model of the Critters world & update the display. Basically, the clients try to be forgiving.
Using this error-forgiving, sloppy client, you'd see a distorted, inaccurate, incomplete view into the Critters world, but I'm hoping it'd be good enough to convey the idea of what's happening in the world.
Along with the real-time viewer client, there could be a Web page that was automatically updated to show the currtent civilization, generation, & population. It could show the DNA, decoded features, & Lisp data for some randomly selected individuals from the current population. It could also show the same information about some record-setting individuals, such as the first, the latest, the longest-lived, & the most-mated. It could show a few hi-rez still pictures from the world. It could be updated about every ten minutes.
Of course, I need to get the simulation running first.
The Lisp source to Critters proper begins in src/critters.lisp.
The program begins with critters-loop. I don't like that; it needs some arguments. One argument should be the world, which consists of all the objects & the event queue (a Flez, probably primed with some events). The display might be an argument, too.
Need some physics. I was experimenting with ideas for physics when I last worked on the program, nearly two weeks ago. There is some code in src/physics.lisp. Also see code in src/thing.lisp. At this point, I think I should start again; some bits of code I've already done should be salvagable. Instead of worrying about realistic physics, I should make-up some physics that are simple to implement.10.4
I've been distracted from this program for nearly a month. The sources of the distraction were .hack, a programming contest, & Ratchet and Clank.
Interesting. I've been reading about MUDs & reading some TinyMUSH source code when I'm not programming Critters. MUDs (TinyMUSH, at least) have a fundamental, recursive, arguably elegant assumption abount containment, & I see that structure taking shape in Critters.
I wanted to post physics collision events. If you don't care about watching a movie of the action, you could post just the events when they happen. If you want to watch a movie, you can make artificial events which are the frames.
It won't work for two reasons.
Some forces are continuous. Gravity is an example. You can't post a gravity event. You must use Euler integration for it. So gravity, electro-static charge, & other continuous forces prevent a purely event-driven model.
Collisions also prevent a purely event-driven model. I thought it would be ultra-cool to detect collisions by treating a position delta as a vector in 4-space (time being one of the components). It'd be tricky, but I'm sure you could twiddle the units of the components so that the simple mathematical formula to locate the intersection between two vectors (which I forget at the moment) could give you the time & location at which the two objects collide. That'd be awesomely clever because you could post the collision as an event &, with a small amount of work in the collision event to ensure that it was still valid, the event queue would automagically execute the first collision but not the others.
The flaw in that idea is that collisions occur in more circumstances than simply when the object centers occupy the same point at the same time. Even if the objects are spheres, it's more complicated than simply finding the closest distance between the position deltas & determining whether the spheres were there at the same time. If the objects are more complex than spheres, then it might be hugely complicated. My gut says that you'd need to do some kind of Euler integration along the position deltas to check for collisions, anyway. If you are going to do Euler integration for that, you might as well use Euler integration for the entire physics simulation, at least because other people have already developed the technique & written code for it.
The viewer works! Well, it's a proto viewer. Had a good time today implementing an automatic camera movement algorithm because I'm tool lazy to implement a user-controlled camera. Or maybe it's not laziness but an appreciation for automation. Anyway, it was fun, & the camera movement is cool now.
Demo0060, which uses a Lisp server program to move a ball & the viewer to display it, gets over 150 frames per second when I run the server on Palsy & the viewer on Plague, connected by a 10 megabit/second Ethernet. I predict that network bandwidth will not be the limiter of frame rate in the finished application.
The viewer has ``classes'' of graphical objects hard-coded into it. I will add more such classes, & eventually add a generic, composite class.
Demo0061 is like demo0060 except that it allows for more spheres bounding around the world. I had to make some minor changes to the viewer program. Had to create a vector library for Lisp (which worked out pretty well). Then copied demo0060-lisp.sh to demo0061-lisp.sh & modified it.
Demo0060 gets about 80 frames per second on Plague until I added a timer mechanism to limit the frame rate to 30 frames per second.10.5 Then the program achieved about 25 frames per second when the Lisp part ran on Palsy & the viewer ran on Plague.
I experimented with more bouncing balls in demo0061. At about ten, it gets about the same frame rate that demo0061 does. At 100 balls, it gets about ten frames per second. At 900, two frames per second. At 2,000 balls, it gets 0.7 frames per second.
The limiting factor proved to be the Lisp program, though the viewer could have ran only about five times faster. A Critter will require a lot more CPU cycles than will a bouncing ball. So at, say, 500 critters in a world, plus about 500 other objects, I suspect I'll get about one frame every ten seconds. That'll be very slow. I had hoped that the Critters world would run faster than the real world if I had the time step set to about 0.1 second. Now, I suspect it will run about one game second every hundred real seconds unless I figure out some way to make it faster.
Moved the physics & some other features from Critters into a new library, Phylis. The new library is not specific to Critters; if I do it right, it'll be useful in other projects.
Inside Phylis, I'm beginning demo0062. It shows bouncing balls, like demo0060 and demo0061, it it uses Phylis's physics & collision engine, where the previous demos used customer, simpler, fake physics engines.