joeldg - navigating the surface

I have a somewhat simple idea I want to make into a game. I ‘know’ that I can do it in PHP with a mix of css/ajax/json tied together with JQuery but I would like it to be something that I do not have to maintain as heavily as a browser app where I need to worry about various browsers and what might be coming along in the next incarnation of Firefox or the dreaded IE (which has been a horrendous thorn in my side on every web project I have ever built). I decided that I should look into a game engine for speed and OMG I entered a whole new world of hobby projects, half-baked ideas, expensive solutions, HUGE specialty engines, paid as your go solutions shamelessly pandered like a vanity press (Torque) and then the do-it-yourself engines.

After reading reviews and actually looking through a WHOLE slough of these various engines I came to the conclusion that like everything else there are ‘tools for the job’ and you need to pick the right tool for the exact job at hand while maintaining flexibility for things that you may need to do later and for growth. It is also helpful to work with languages and tools you currently know and enjoy working with. So I came up with some basics for what I need for my project because picking a game engine is perhaps one of the single most important parts of coding a game.

1. Cross platform - windows/linux/mac in that order of preference with at least win/linux
2. scriptable - Lua/Squirrel or Python bindings with good network support
3. large and active community - Busy forums that are helpful where people share code (I personally like to share code when I solve a particularly vexing problem)
4. ability to handle 3d - but NOT specifically a FPS engine (this was a major issue with a lot of the engines I looked at), I am much more interested in third person and or 3d/iso’ish with bounded-selects for my particular game.
5. Free or very cheap - Why on earth would I want to pay a lot of money for something that I would then be limited in my ability to share my enhancements with the community later? (especially when this is a small project with one coder) There are many other ways to make money on software.. Host servers for games, write books, paid support contracts etc.
6. Speed of use and decent learning curve - I do not want to spend a year learning some crazy API or some language some developers made up to create their own games.
7. No click and drag / piecemeal engines - I.E. If an engine states that you just need to click together parts and then fill in some info to create your game I get really suspicious.
8. Customizable - Why would I want my game to look just like someone else’s game and have reviews go “Oh this game is just like ___ but acts sort of like ___ don’t bother because you have seen it all before”

Once I started comparing a lot of the engines to my list they dropped off like flies. So in the end, because of my particular needs and want of simplicity, I was left with OGRE3d and Irrlicht, both of which fit the bill nicely and are well documented and used render engines that are not specifically boxed into one corner or another or limited by insane design schemes and/or unusable for my purposes. While being somewhat simple (Irrlicht is dead simple and I would highly recommend for hacking out quick 3d visualizations). Both engines are specifically for C++, which is all good but after taking a nice close look at my projects needs, and the fact that it really is not that complex graphically, working with optimized C++ is really not a big need as I am thinking I might have at most 20 characters/models on my screen at the most and the rest will interface changes that are done via network. Having to comb through the myriad of C++ libraries that I am only passingly familiar with and having to learn their syntax, quirks and funky compile issues all while ‘also’ learning a render engine left me with a foul taste in my mouth. However I pressed on and started to brush up on my C++ (which I have not used Visual C++ or Code::Blocks in a very long time and both these have changed dramatically since my last foray into C++). Then, I ran across something interesting while perusing the OGRE wiki.

PyOgre is a python binding to Ogre and I started looking into it and thought to myself “hey, I know python and I know a lot of the libraries as well.. this could speed up my development time.. hrm”. PyOgre bindings hook directly into the Ogre libs and Python runs anywhere. This might actually fit the bill, it easily fits into my list of needs and is lightweight enough and has a very good learning curve for me. So to be thorough off I went to the python game resources on the python site and I decided to look into the other engines that are out there for python that may been an even better fit for my particular needs. Most of these are HIGHLY specialized libs for doing things like math visualization or specific bindings to other engines I had already thrown out. Then while combing through the list I found ONE engine (unfortunately) named Panda3D (also see the wikipedia article) (it rises above it’s cheeseball name upon inspection) that seems like a decent fit and I am now in early stage playing around with it. So far I have found sample code for almost all the elements of the game I want to create and it appears to have the full features of other engines as well, though I would not be locked into having to deal with more than I want and can easily crank out a server app using stackless python (which on a low end box could handle many more clients than I could probably find for my game)

So finally at the end of two weeks of downloading, compiling and trying out engines, attempting to interact with the various communities and ducking shyster companies that want to nickel and dime every naive, hobby or wanna-be game maker (which by the way I find deplorable as some companies could actually be discouraging a lot of potential talent from actually creating their games by doing this, thus hurting the industry as a whole) *cough* Torque *cough* I have found that I came full circle back to python (pygame was the first engine I worked on the initial stages of this idea, that was three years ago) and ended up blending some preconceptions I naively had about game engines.

I am left with a choice between two engines that are different but fit the bill.
On one hand I have the very open ended and extensible OGRE via PyOGRE which it easy enough to be up and running with and on the other I have Panda 3d which already has many of the Pathfinding, audio, animation and import modules I need but I could extend it out quickly (and if I want can also program in C++ for parts or all of it)
In a straight comparison to be up and running quickly I am leaning towards Panda3d but I am still doing a little research into PyOGRE. Hopefully my next post I will plop some code and screen shots in here.

In the meantime, I hope this post saves someone some time their search for an engine for a game that is NOT an FPS (sorry they all look the same to me now, and are boring) but it not some 2d 1990 nintendo looking mess.
If you looking to build an RTS (real time strategy) or simulation style game (think ISO’ish) I would recommend you look into what Python has to offer.

Been a while since making a post here. Since my last post I have been working as a Sysadmin and programmer for a new company and am currently working on a web version of a music artist ‘wall’ (code name) which is basically a web itunes with artist info and all ajaxified.

I recently took a trip to Shanghai and posted some pictures of my trip, it was a lot of fun and got to see some amazing sights. The jet-lag however was brutal and took days to recover from.

In other news SOTNW is a blast of a game and has managed to suck some of my time that otherwise would have been spent on “my” game project that I have been tooling with here and there.

I will be writing more in the coming days as I will be diving back into a lot of new and exciting work.
As a side note: Anime Spinner is still kicking and being added to all the time.. (Make sure to check out the DEMO which is right under the flash block at the top and watch it for a little bit to see how it all works, also if you sign up for an account you can watch the anime full screen)

The problem: Most current cell phones (except exceptionally new ones) do not come with built in GPS devices. Phones do however connect to radio towers within range, which broadcast ID’s. I am interested to determine if there is an easier way to generate lat/long location from radio towers, instead of using a bluetooth GPS device, by using inference from publically accessible data and geocoding, combined with the cell tower ID broadcast to my phone.

In many countries the latitude and longitude of cell towers is public data. In the US it is public sort of, when registering with FCC, the companies do not need to register the broadcast cell-id which is transmitted to the phones. To make matters more complex, different cell companies can broadcast different ID’s from the same towers. From this, many different projects have popped up to attempt to map cell-id to latitude and longitude. They work, I assume, to refine the results for each tower. The good news is, is that the FCC being a public entity is bound by the freedom of information act and must publish (even in a nasty form) it’s data. The FCC provides a large database of the exact location of towers, but we just don’t know what those towers are called and who uses them.

The idea here is that we can make some educated guesses in an attempt to refine the FCC data with what little information we are given by the tower itself and some simple server-side geocoding. Basically we are going hack the cell-id’s ‘into’ the FCC data, which we must assume will have missing towers and incomplete data as the requirement to register a tower only applies to certain tower types and array heights.

If you read my post about working with lat/long pairs in mysql and doing great circle searches, then you may find the following code snippets interesting as it is to work with doing computation on latitude and longitude. I worked these out by porting some and reading some math forums, they will come in handy for inferring my location in proximity of cell towers.

First we have a few support functions, converting to radians, and converting between lat/long types (Degree/minute/second format to degree’s and back):

function rad($v){
return ($v*M_PI/180);
}

/*
degree,minute,seconds to decimal degrees
note: this could also be done in a single line using ternary
*/
function dms2deg($D,$M,$S,$dir){
if(strpos(‘ WsSs’, $dir)>0){
return(-1 * ($D + ($M + $S/60)/60));
}else{
return($D + ($M + $S/60)/60);
}
}
function dms($rad) {
$d = abs($rad * 180 / M_PI);
$d += 1/7200; // add ½ second for rounding
$deg = floor($d);
$min = floor(($d-$deg)*60);
$sec = floor(($d-$deg-$min/60)*3600);
// add leading zeros if required
if ($deg< 100) $deg = ‘0′ + $deg;
if ($deg< 10) $deg = ‘0′ + $deg;
if ($min< 10) $min = ‘0′ + $min;
if ($sec< 10) $sec = ‘0′ + $sec;
return $deg + ‘\u00B0′ + $min + ‘\u2032′ + $sec + ‘\u2033′;
}

These are used in the following functions. First one thing we must have the ability to do is to determine the distance between two points on the map. We can use the following PHP function to do this:

/*
distance between two points using sherical law of cosines
cos c = cos a cos b + sin a sin b cos C
*/
function distance($lat1, $lon1, $lat2, $lon2, $units = ‘miles’){
$lat1 = rad($lat1); $lon1 = rad($lon1);
$lat2 = rad($lat2); $lon2 = rad($lon2);
switch ($units){
case “miles”: $r = 3963.1; break;;
case “nmiles”: $r = 3443.9; break;;
case “kilo”: $r = 6378; break;;
}
// this is another way to do it
#$rv = pi()/180;
#$a1 = $lat1 * $rv; $b1 = $lon1 * $rv;
#$a2 = $lat2 * $rv; $b2 = $lon2 * $rv;
#return (acos(cos($a1)*cos($b1)*cos($a2)*cos($b2) + cos($a1)*sin($b1)*cos($a2)*sin($b2) + sin($a1)*sin($a2)) * $r);

return acos(sin($lat1)*sin($lat2) + cos($lat1)*cos($lat2)*cos($lon2-$lon1)) * $r;
}

Next, it would be helpful to know the bearing from one point to another point.

/*
initial bearing from point 1 to point 2
*/
function bearing($lat1,$lon1, $lat2, $lon2) {
$y = sin($lon2-$lon1) * cos($lat2);
$x = cos($lat1)*sin($lat2) - sin($lat1)*cos($lat2)*cos($lon2-$lon1);
return atan2($y, $x);
}

We also would like to be able to find the exact midpoint between two points,

/*
find out what the midpoint between two points is
*/
function midpoint($lat1, $lon1, $lat2, $lon2) {
$lat1 = rad($lat1); $lon1 = rad($lon1);
$lat2 = rad($lat2); $lon2 = rad($lon2);
$dLon = $lon2 - $lon1;
$Bx = (cos($lat2) * cos($dLon));
$By = (cos($lat2) * sin($dLon));
$lat3 = atan2( sin($lat1) + sin($lat2), sqrt( (cos($lat1)+$Bx) * (cos($lat1)+$Bx) + ($By * $By)) );
$lon3 = $lon1 + atan2($By, cos($lat1) + $Bx);

if (!$lat3 || !$lon3) return false;
return array($lat3 * 180 / M_PI, $lon3 * 180 / M_PI);
}

Now that we can have some functions to work lat/long pairs we need to see how to put things together. I am going to use the following image to help explain some concepts first:

In this bad image, the 1-5 is the path we take and what we can see happening at each spot of our path. the lower-case letters are cell towers that might be broadcasting to us, but we only have a row in the FCC database knowing that a tower IS there, the uppercase ones are towers we know nothing of. We we have a little app (that will not be public just yet) that run all the time and notifies us with a beep when it finds a new cell-id and we then stop where we are and type in the nearest address which the server goecodes to our location with the cell-id’s and signal strength.

POINT 1, central park: We can see cell tower “a”, we geocode our location and mark down in the database that tower “a” is within range of the geocoded location we are at, all is good, and this is about as far as anyone has gotten so far. We run a great circle search from our location and mark the towers near us with the cell-id “a” and also make a note of the signal strength.
POINT 2, west side : We pick up an unknown tower “D” we mark it down along with a geocoded location, we also pick up “a” again and mark it again, along with signal strength and provide towers within our great circle the cell-id info. This helps refine ‘a’ but we assume we are further out as the signal strength is lower.

POINT 3, hells kitchen: we now pick up another tower “b” which we can mark in the database, we also pick up “a” within this, however both have low signal strength, we mark both with the cell-id’s and signal strength. And we can figure that we are about halfway between ‘a’ and ‘b’ we can also make some guesses about direction being travelled by using our current point along with current cell and more than one reading.
POINT 4, West village: Now we only have tower “b”, we mark this tower known with strength and it is known so again we are just confirming it’s presence.

POINT 5, Fulton street: again we have a known tower ‘c’, we mark it along with the signal strength, our prior mark was with tower ‘b’ we can infer by signal strength and our prior location that we should be about halfway between ‘b’ and ‘c’

A lot of this data can be refined as we go, but as you can see, with only a few real points and a few cell towers we can gather a lot of location data, also, we can keep a live map of our locations and where we have travelled. In some areas we can get location to within a reasonable degree that we could zoom a map to street level close by.

In an area such as Manhattan with the intense cell coverage, we can quickly refine our location to a reasonable area and pinpoint which row in the FCC database cooresponds to which cell-id by just walking around for a few minutes. In more rural areas this might be a slightly more interesting problem, but if you mark your headings as you travel we could even determine your location on the map by your speed and bearing.