Tuesday, December 14

How network games work...

Highly handy comment from PlayerController.uc in the Unreal Development Kit: Multiplayer net games 101..

Here's how player movement prediction, replication and correction works in network games:

Every tick, the PlayerTick() function is called. It calls the PlayerMove() function (which is implemented
in various states). PlayerMove() figures out the acceleration and rotation, and then calls ProcessMove()
(for single player or listen servers), or ReplicateMove() (if its a network client).

ReplicateMove() saves the move (in the PendingMove list), calls ProcessMove(), and then replicates the move
to the server by calling the replicated function ServerMove() - passing the movement parameters, the client's
resultant position, and a timestamp.

ServerMove() is executed on the server. It decodes the movement parameters and causes the appropriate movement
to occur. It then looks at the resulting position and if enough time has passed since the last response, or the
position error is significant enough, the server calls ClientAdjustPosition(), a replicated function.

ClientAdjustPosition() is executed on the client. The client sets its position to the servers version of position,
and sets the bUpdatePosition flag to true.

When PlayerTick() is called on the client again, if bUpdatePosition is true, the client will call
ClientUpdatePosition() before calling PlayerMove(). ClientUpdatePosition() replays all the moves in the pending
move list which occured after the timestamp of the move the server was adjusting.

Wednesday, December 1

Unrealscript Mode for Emacs Reloaded

I actually started picking up Unreal again, and Unrealscript. My previous attempt at an Unrealscript mode was badly flawed. It was based on CC-mode, which I did not fully pursuade to understand the syntax of Unrealscript. This time, I've gone back to first principles and created simple progmode not derived from cc-mode. This means a loss of functionality, but it does mean correct indenting, and true case insensitivity. I found CC mode would have to be patched to handle a case insensitive language like UnrealScript. Anyway, without further ado, here it is. I reccomend it over the previous ones.

(defvar unrealscript-mode-hook nil)

(defvar unrealscript-mode-map
(let ((unrealscript-mode-map (make-sparse-keymap)))
(define-key unrealscript-mode-map "\C-j" 'newline-and-indent)
"Keymap for UNREALSCRIPT major mode")

(defconst unrealscript-font-lock-keywords-1
'("\\<\\(?:break\\|c\\(?:\\(?:as\\|ontinu\\)e\\)\\|do\\|e\\(?:lse\\|xtends\\)\\|for\\(?:each\\)?\\|i\\(?:f\\|nterface\\)\\|new\\|return\\|switch\\|var\\|while\\|class\\)\\>" . font-lock-keyword-face))
"Minimal highlighting expressions for UNREALSCRIPT mode.")

(defconst unrealscript-font-lock-keywords-2
(append unrealscript-font-lock-keywords-1
'("\\<\\(?:array\\|b\\(?:ool\\|yte\\)\\|c\\(?:lass\\|o\\(?:erce\\|lor\\|ords\\)\\)\\|de\\(?:faultproperties\\|legate\\)\\|e\\(?:num\\|vent\\)\\|f\\(?:alse\\|loat\\|unction\\)\\|int\\|local\\|name\\|o\\(?:ptional\\|ut\\)\\|plane\\|r\\(?:egion\\|otator\\)\\|st\\(?:ate\\|r\\(?:ing\\|uct\\)\\)\\|true\\|v\\(?:\\(?:a\\|ecto\\)r\\)\\)\\>" . font-lock-keyword-face)))
"Additional Keywords to highlight in UNREALSCRIPT mode.")

(defconst unrealscript-font-lock-keywords-3
(append unrealscript-font-lock-keywords-2
'("\\<\\(?:A\\(?:bstract\\|llowAbstract\\|uto\\(?:Comment\\|ExpandCategories\\)\\)\\|Co\\(?:llapseCategories\\|nfig\\)\\|D\\(?:ep\\(?:endsOn\\|recated\\)\\|isplayName\\|ontCollapseCategories\\)\\|Edit\\(?:Condition\\|InlineNew\\)\\|FriendlyName\\|Hide\\(?:Categories\\|DropDown\\)\\|I\\(?:\\(?:mplemen\\|nheri\\)ts\\)\\|N\\(?:ative\\(?:Replication\\)?\\|o\\(?:Export\\|nTransient\\|t\\(?:EditInlineNew\\|Placeable\\)\\)\\)\\|P\\(?:erObject\\(?:Config\\|Localized\\)\\|laceable\\)\\|ShowCategories\\|T\\(?:oolTip\\|ransient\\)\\|Within\\)\\>" . font-lock-type-face)
'("\\<\\(?:auto\\|c\\(?:lient\\|on\\(?:fig\\|st\\)\\)\\|d\\(?:atabinding\\|eprecated\\|uplicatetransient\\)\\|e\\(?:dit\\(?:const\\|fixedsize\\|inline\\(?:use\\)?\\|oronly\\)\\|x\\(?:ec\\|port\\)\\)\\|globalconfig\\|i\\(?:gnores\\|n\\(?:it\\|put\\|stanced\\|terp\\)\\|terator\\)\\|l\\(?:atent\\|ocalized\\)\\|n\\(?:ative\\(?:replication\\)?\\|o\\(?:clear\\|export\\|import\\|ntransactional\\|tforconsole\\)\\)\\|operator\\|p\\(?:o\\(?:\\(?:inte\\|stoperato\\)r\\)\\|r\\(?:eoperator\\|ivate\\|otected\\)\\|ublic\\)\\|re\\(?:liable\\|pnotify\\)\\|s\\(?:erver\\|i\\(?:mulated\\|ngular\\)\\|kip\\|tatic\\)\\|tra\\(?:nsient\\|vel\\)\\|unreliable\\)\\>" . font-lock-keyword-face)
'("\\<\\(?:A\\(?:bs\\|cos\\|dd\\(?:Item\\)?\\|llActors\\|s\\(?:c\\|in\\)\\|tan\\)\\|B\\(?:asedActors\\|egin\\(?:Play\\|State\\)\\)\\|C\\(?:aps\\|eil\\|h\\(?:ildActors\\|r\\)\\|l\\(?:amp\\|earTimer\\)\\|o\\(?:\\(?:llidingActor\\)?s\\)\\)\\|D\\(?:estroyed\\|i\\(?:\\(?:sabl\\|vid\\)e\\)\\|ynamicActors\\)\\|E\\(?:mpty\\|n\\(?:\\(?:abl\\|dStat\\)e\\)\\|val\\|xp\\)\\|F\\(?:Clamp\\|M\\(?:ax\\|in\\)\\|Rand\\|astTrace\\|in\\(?:d\\|ish\\(?:Anim\\|Interpolation\\)\\)\\)\\|G\\(?:etTimer\\(?:Count\\|Rate\\)\\|oTo\\(?:State\\)?\\)\\|I\\(?:n\\(?:Str\\|itGame\\|sert\\(?:Item\\)?\\|vert\\)\\|s\\(?:\\(?:InStat\\|TimerActiv\\)e\\)\\)\\|L\\(?:e\\(?:ft\\|n\\|rp\\)\\|o\\(?:cs\\|ge\\)\\)\\|M\\(?:ax\\|i\\(?:rrorVectorByNormal\\|[dn]\\)\\)\\|Normal\\|OverlappingActors\\|P\\(?:o\\(?:pState\\|stBeginPlay\\)\\|reBeginPlay\\|ushState\\)\\|R\\(?:and\\|e\\(?:move\\(?:I\\(?:ndex\\|tem\\)\\)?\\|pl\\(?:ace\\)?\\)\\|ight\\|ound\\)\\|S\\(?:et\\(?:State\\|Timer\\)\\|in\\|leep\\|merp\\|p\\(?:awn\\|lit\\)\\|q\\(?:rt\\|uare\\)\\)\\|T\\(?:an\\|ick\\|ouchingActors\\|race\\(?:Actors\\)?\\)\\|V\\(?:Rand\\|Size\\|isible\\(?:\\(?:Colliding\\)?Actors\\)\\)\\|\\(?:ro\\|vec\\)t\\)\\>" . font-lock-function-name-face)))
"Balls-out highlighting in UNREALSCRIPT mode.")

(defvar unrealscript-font-lock-keywords unrealscript-font-lock-keywords-3
"Default highlighting expressions for UNREALSCRIPT mode.")

(defvar unrealscript-indent-width 4)

(defun looking-at-unrealscript-indent-keyword ()
(or (looking-at "^[\t ]*while") (looking-at "^[\t ]*if") (looking-at "^[\t ]*else") (looking-at "^[\t ]*for")))

(defun looking-at-unrealscript-block-end ()
(or (looking-at "^[\t ]*end") (and (looking-at "^.*}[ \t]*$") (not (looking-at "^.*{")))))

(defun looking-at-unrealscript-block-start ()
(or (looking-at "^[\t ]*begin") (and (looking-at "^.*{") (not (looking-at "^.*}[ \t]*$")))))

;; Function to control indenting.
(defun unrealscript-indent-line ()
"Indent current line as Unrealscript code"
;; Set the point to beginning of line.
(if (bobp)
(indent-line-to 0)
(let ((not-indented t) (lines-back 0) cur-indent)
(if (looking-at-unrealscript-block-end) ; Check for closing brace
;; if we are at the end of a block
(forward-line -1)
(setq lines-back (+ lines-back 1))
(setq cur-indent (- (current-indentation) unrealscript-indent-width)))
;; Safety check to make sure we don't indent negative.
(if (< cur-indent 0)
(setq cur-indent 0)))
;; else scan backward
(if (looking-at-unrealscript-block-start) ; Opening block
(forward-line -1)
(setq lines-back (+ lines-back 1))
(setq cur-indent (current-indentation))
(setq not-indented nil))
(while not-indented
(forward-line -1)
(setq lines-back (+ lines-back 1))
(if (looking-at-unrealscript-block-end) ;; Closing Block
(setq cur-indent (current-indentation))
(setq not-indented nil))
(if (looking-at-unrealscript-block-start)
(setq cur-indent (+ (current-indentation) unrealscript-indent-width))
(setq not-indented nil))
(if (looking-at-unrealscript-indent-keyword)
(setq cur-indent (current-indentation))
(forward-line 1)
(setq lines-back (- lines-back 1))
(if (looking-at-unrealscript-block-start)
(setq not-indented nil) ;; has block
(if (zerop lines-back) ;; no block
(setq cur-indent (+ cur-indent unrealscript-indent-width))
(setq not-indented nil))
(setq not-indented nil))))
(if (bobp)
(setq not-indented nil)))))))))
(if cur-indent
(indent-line-to cur-indent)
(indent-line-to 0)))))

(defun unrealscript-populate-syntax-table (table)
"Populate the given syntax table as necessary for a C-like language.
This includes setting ' and \" as string delimiters, and setting up
the comment syntax to handle both line style \"//\" and block style
\"/*\" \"*/\" comments."

(modify-syntax-entry ?_ "_" table)
(modify-syntax-entry ?\\ "\\" table)
(modify-syntax-entry ?+ "." table)
(modify-syntax-entry ?- "." table)
(modify-syntax-entry ?= "." table)
(modify-syntax-entry ?% "." table)
(modify-syntax-entry ?< "." table)
(modify-syntax-entry ?> "." table)
(modify-syntax-entry ?& "." table)
(modify-syntax-entry ?| "." table)
(modify-syntax-entry ?\' "\"" table)
(modify-syntax-entry ?\240 "." table)

;; Set up block and line oriented comments. The new C
;; standard mandates both comment styles even in C, so since
;; all languages now require dual comments, we make this the
;; default.
(modify-syntax-entry ?/ ". 124b" table)
(modify-syntax-entry ?* ". 23" table)

(modify-syntax-entry ?\n "> b" table)
;; Give CR the same syntax as newline, for selective-display
(modify-syntax-entry ?\^m "> b" table)

(defvar unrealscript-mode-syntax-table
(let ((unrealscript-mode-syntax-table (unrealscript-populate-syntax-table (make-syntax-table))))
"Syntax table for unrealscript-mode")

(defun unrealscript-mode ()
"Major mode for editing Unrealscript files"
(set-syntax-table unrealscript-mode-syntax-table)
(use-local-map unrealscript-mode-map)
(setq indent-line-function 'unrealscript-indent-line)
(setq font-lock-defaults '(unrealscript-font-lock-keywords nil t))
(setq major-mode 'unrealscript-mode)
(setq mode-name "UNREALSCRIPT")
(run-hooks 'unrealscript-mode-hook)
(setq case-fold-search t)
(setq font-lock-keywords-case-fold-search t))

(provide 'unrealscript-mode)

Wednesday, September 15

A micro manual for Lisp in C++

It was with some interest that I read A Micro Manual for Lisp in C. One thing I have noticed about such efforts is that they are nearly always implemented in idiomatic C. I thought (out of idle curiosity, mainly) I'd see what a similar thing implemented in idomatic C++ would look like.

The main practical advantage that it offered in the end was the fact that boost::shared_ptr gave me rudimentary garbage collection for free. I used boost::variant to give me polymorphic lisp objects and thus did not have to use naked pointers anywhere, which seems to me to be an improvement in code safety. The price of this is a nosier syntax. You pay your money and you takes your choice..

As a concrete example here is what the implementation of CONS looked like.

boost::shared_ptr<lisp::object> fn_cons(boost::shared_ptr<lisp::object> args,
boost::shared_ptr<lisp::object> env) {

boost::shared_ptr<lisp::object> list = make_cons(car(args), boost::shared_ptr<lisp::object>());
args = car(cdr(args));

while ((args != NULL) && (args->which() == lisp::e_CONS)) {
append(list, car(args));
args = cdr(args);
return list;

Its probably also worth noting that avoiding naked pointers meant using boost::function for function objects, thusly..

enum kind {
e_ATOM = 0,

struct atom {
std::string name;

atom(const std::string& n) : name(n) {

struct cons {
boost::shared_ptr<object> car;
boost::shared_ptr<object> cdr;

cons(boost::shared_ptr<object> first, boost::shared_ptr<object> second) : car(first), cdr(second) {


typedef boost::function< boost::shared_ptr<object> (boost::shared_ptr<object>,boost::shared_ptr<object>) > lisp_func;

struct func {
lisp_func fn;

func(const lisp_func& f) : fn(f) {


struct lambda {
boost::shared_ptr<object> args;
boost::shared_ptr<object> sexp;

lambda(boost::shared_ptr<object> a, boost::shared_ptr<object> s) : args(a), sexp(s) {


typedef boost::variant< atom, cons, func, lambda > base_object;

And creating the environment like so...

boost::shared_ptr<lisp::object> init_env() {

boost::shared_ptr<lisp::object> nul;

boost::shared_ptr<lisp::object> a_quote(new lisp::object(std::string("QUOTE")));
boost::shared_ptr<lisp::object> f_quote(new lisp::object(fn_quote));

boost::shared_ptr<lisp::object> a_car(new lisp::object(std::string("CAR")));
boost::shared_ptr<lisp::object> f_car(new lisp::object(fn_car));

boost::shared_ptr<lisp::object> a_cdr(new lisp::object(std::string("CDR")));
boost::shared_ptr<lisp::object> f_cdr(new lisp::object(fn_cdr));

boost::shared_ptr<lisp::object> a_cons(new lisp::object(std::string("CONS")));
boost::shared_ptr<lisp::object> f_cons(new lisp::object(fn_cons));

boost::shared_ptr<lisp::object> a_equal(new lisp::object(std::string("EQUAL")));
boost::shared_ptr<lisp::object> f_equal(new lisp::object(fn_equal));

boost::shared_ptr<lisp::object> a_atom(new lisp::object(std::string("ATOM")));
boost::shared_ptr<lisp::object> f_atom(new lisp::object(fn_atom));

boost::shared_ptr<lisp::object> a_cond(new lisp::object(std::string("COND")));
boost::shared_ptr<lisp::object> f_cond(new lisp::object(fn_cond));

boost::shared_ptr<lisp::object> a_lambda(new lisp::object(std::string("LAMBDA")));
boost::shared_ptr<lisp::object> f_lambda(new lisp::object(fn_lambda));

boost::shared_ptr<lisp::object> a_label(new lisp::object(std::string("LABEL")));
boost::shared_ptr<lisp::object> f_label(new lisp::object(fn_label));

boost::shared_ptr<lisp::object> env = make_cons(make_cons(a_quote,make_cons(f_quote,nul)),nul);

append(env,make_cons(a_car, make_cons(f_car,nul)));
append(env,make_cons(a_cdr, make_cons(f_cdr,nul)));
append(env,make_cons(a_cons, make_cons(f_cons,nul)));
append(env,make_cons(a_equal, make_cons(f_equal,nul)));
append(env,make_cons(a_atom, make_cons(f_atom,nul)));
append(env,make_cons(a_cond, make_cons(f_cond,nul)));
append(env,make_cons(a_lambda, make_cons(f_lambda,nul)));
append(env,make_cons(a_label, make_cons(f_label,nul)));

boost::shared_ptr<lisp::object> a_tee(new lisp::object(std::string("#T")));
tee = a_tee;
nil = make_cons(nul,nul);

return env;

Wednesday, August 11

OpenGL Development on Windows with Slime

I've been playing with OpenGL, Common Lisp (SBCL, CCL, Lispworks Personal) and SLIME again. Mostly I've been establishing a S-Expression exporter for Blender so I can export entire scenes to the engine I'm working on.

I did discover some wrinkles of working on OpenGL development with SLIME in Windows. CCL uses the :spawn communication style in SLIME which uses it's multi-threaded nature to run each repl request in a seperate thread from the executing lisp code. So if you have your OpenGL app running in the background as you develop it, if you write an experimental form at the repl that includes OpenGL calls, its going to fail, since it will not be executing in the main OpenGL thread.

The solution is to fall back on the nil communication style, which is not threaded and is blocking. This has the less than desirable effect of blocking your repl until the executing app finishes. This can be circumvented by calling swank-handle-requests - like so

(initially (progn ,init-forms))
(skip-photons-loop "Skip photons loop body")
(skip-swank-request "Skip swank evaluation")
(let ((connection
(or swank::*emacs-connection* (swank::default-connection))))
(swank::handle-requests connection t)))
(until ,exit-test)
(finally (progn ,exit-forms))))

There are actually some subtelties here. The skip-photons-loop restart allows you to recover from an error in the loop body, by recompiling the offending form, when the handle-requests function is called, while the skip-swank-request restart allows you to recover from entering an invalid form at the repl without losing the application.