After finishing my final year at university I felt that the ‘AI for games’ module did not teach us sufficiently, it concentrated more on theory rather than using a kinaesthetic, practical hands on approach. So I decided to find a project that I could undertake to try and bolster my knowledge.
In my spare time I like to play Eve Online, a futuristic, space based (single shard) MMORPG.
The player resides in their very own futuristic spaceship, rather than having the conventional humanoid avatar. This can be changed to better suit the needs of a specific task, as well as upgrading and modifying it as they wish.
Eve prides itself with its player community, player run economics and game world; resulting in probably the most complex MMORPG around at the moment.
Furthermore, it encourages 3rd party applications, websites and tools to be created to aid players performing different in-game and out of game tasks related to Eve. This is accomplished in part by having a specific forum for players and developers to discuss ideas and tools. Also, Eve has an API along with ‘static data dumps’ which allows developers to gain access to in game data.
The back story:
Eve is set in a vast, sand-box-like galaxy of 1000’s of solar systems; all interconnected to each other through celestial objects called ‘Star gates’. These allow player to transverse the galaxy in their spaceship from system to system known as ‘jumping’.
Corporations (a group of players, similar to clans or guilds) can claim certain systems as their own which is called ‘holding sovereignty’, as you can imagine there is a lot of PVP amongst rival corporation to take and hold these systems. Once a corporation holds sovereignty over a system they can place player made celestial objects called ‘Jump bridges’, these act the same as Star gates but the players can chose their destination system (within a certain range, they must hold sovereignty and have a Jump bridge in each system). Jump bridges are fundamental to a large Alliance’s (a group of Corporations) infrastructure as it allows players to transverse their held sovereignty quickly, easily and in relatively safety.
The Eve client has an inbuilt path finder that players can use as an aid when travelling between systems; this is displayed visually in-game on a 3D star map. However, this does not that into account any Jump bridges. An example of this is: if a player wanted to go from system A to J they would have to use the route A->B->C->D->E->F->G->H->I->J (a total of 9 jumps). Whereas there could be a Jump bridge between system A and H, allowing the player to complete the journey in 4 jumps (A->H->I->J). However, this is not presented to the player when using the in-game map.
This is where the problem occurs; this is just one simple example containing only one Jump Bridge, whereas in reality there could be scores of systems and multiple jump bridges. Currently Alliances use a static image called a ‘Jump bridge map’ (an example here) to represent their Jump bridge network. Players then either download this or view it from a website and then work out a route by hand. Player owned systems are always obscure names, containing alphanumerics and up to one hyphen, such as GE-8JV.
These static images have a number of flaws:
- They take time to modify/update, which is done very infrequently and normally by a single person.
- They often have inconsistencies of Jump bridge locations.
- They are not centralized; a coalition can have multiple Jump bridge maps which confuses the issue.
- The major issue is that it is an unnecessary time sink. Players have to spend time searching for the start and destination systems, then working out a route (which may not always be optimal).
How did I solve this?
So one night I decided to make a tool to solve this problem. It suited my goal of finding some AI related to games:
- A problem that a lot of people faced
- Directly related to games
- A core fundamental of AI (path finding)
- Non trivial, required some decent programming
- Something new to learn
First of all I needed a list of all the systems in Eve and their connections to their surrounding systems, this is what the ‘static data dump’ provided; a snippet is shown below.
Systems can be thought as nodes and the connections as edges, this is the perfect candidate for a D Star search algorithm. As a Jump bridge is fundamentally the same as a Star gate, a node-edge model can also be used.
- Users inputs two solar system names, the start and destination system.
- Validates the input, converting them to system ID’s and checking if those systems exist.
- Checks a cache table in the database to see if the route has been requested before.
If it’s not in the cache:
- Retrieves all the system connections from the database (Jump bridges included) and constructs an associative array.
- Performs a D* search on the connection array, finding the shortest route, outputting a list of systemID’s.
- Inserts the produced route into the cache table, and also a reversed version of the route; as route A ->B is the same as B -> A.
If it is in the cache:
- Retrieves the route from the cache into a list of systemID’s
- Walks through this list of systemID’s, getting the system’s name as well as checking if the connection was using a Jump bridge; and if so, getting the location of the Jump bridge.
- This is then packaged up and formatted in to a user friendly representation and displayed to the user.
- Jump bridge maps have been scrapped, locations are now stored in a web based database.
- Jump bridge locations are all centralized, in one database. Players only need to go to one site and that’s it.
- Adding, Deleting, Modifying Jump bridges is simple and fast, which be done by multiple people if needed.
- Everything is automated, all the player has to do is enter their start and destination systems and it will work out the fastest route and display it to them.
- When entering systems, the input fields will auto complete to help the users.
- It works for anywhere in the Eve Universe, the start and destination systems could be on complete opposite ends of the universe and it will be able to find a route.
- Results are instant, saving a great amount of time.
- Uses a D* search algorithm, as its dynamic, any changes to the Jump bridges are reflected in returned results instantly.
- Routes are cached so a subsequent request for that same route bypasses all of the heavy crunching of the D star algorithm, and instead, the cached route is extracted and formatted for the user. The cache is cleared when Jump bridges are added or removed.
- Players can also link each other routes through the use of PHP GET parameters. For example: http://aaa.evejb.com/index.php?from=Jita&to=GE-8JV
It is currently being used by one of the largest alliances in Eve (my alliance), ‘Against All Authorities’ and their coalition. To see the site in action head over to: http://aaa.evejb.com
- From: Jita
- To: GE-8JV
Hint: Try using other systems by entering random alphanumerics into the start and end boxes, the autocomplete feature will find a system for you.
The tool came into its own when the game makers released a game update which restricted systems to only have one jump bridge (rather than two). This required all alliances with Jump bridges to restructure their entire network. As new Jump bridges were being placed players were able to find up-to-date routes without having to hunt or wait for new Jump bridge maps to be created; also, they didn’t have to relearn a whole new network with 40 Jump bridges in it.
This scenario is later repeated in war time, when alliances are fighting each other, like all good strategies, infrastructure is hit first resulting in Jump bridges being destroyed and the network being changed to accommodate this.
So within a couple of hours I created an elegant webpage and a D* path finding algorithm in PHP. Saving players a great amount of time and effort, as well as reducing the logistical burden of keeping the network up-to-date. All in all I fell this mini project was a success as it fulfilled my goals and I gained new skills and knowledge.
- Frontend: HTML / CSS / jQuery / Ajax
- Backend: PHP 5 / MySql
- Route Requests: ~30,000 (at the time of posting, in 6 months)
- Requests per day: ~150-200
- Algorithm: D*
- Nodes: ~ 6000
- Edges: ~ 15000
Execution time on a 100 jump route (one side of Eve to the other, non-cached): ~0.1 seconds