Project Title: Pathfinder AI

Student: Abhishek Jha

Organization: Python Software Foundation


Introduction

One of the most important requirement of a game is to move units around sensibly. So it makes sense to have built-in support for movement AI in a game engine. Our Navigator controller would allow a game programmer using PySoy to add decent movement AI to his game. Initially the Navigator controller would support pathfinding and simple steering behavior like seek, evade, follow etc. In future it can be extended to support complex steering behaviors and flocking.

Detail

Navigator would be implemented as a pysoy controller. It could be used similar to how keyboard and mouse controller are used. Navigator constructor would take a map and a unit as input. Map object contains map data and location of other units. We can have different types of maps for different types of games. Side-scrolling games would have different maps then FPS or RTS game.

>>>nav = soy.controllers.Navigator(map, vehicle)

Vehicle is the entity controlled by navigator. User would inherit from base vehicle to create his own units/vehicles.

Properties of vehicle

  • mass
  • melocity
  • acceleration
  • radius -- For obstacle avoidance
  • maxSpeed
  • maxForce -- What max. force can be applied.

Navigator would use applyForce() method of the vehicle to move it.

Some of the methods provided by Navigator.

  • moveTo(position)
  • follow(path)
  • seek(vehicle2)
  • evade(vehicle2)

Navigator can be paused or resumed. This would allow us to stop or restart the movement of unit.

>>>navigator.stop()
>>>navigator.start()

Algorithm

For path finding Navigator would use A* algorithm. A* is standard algorithm for path finding.

Schedule

Start of Program (May 24)

Tasks to complete:

· Familiarize with Orc and Genie

· Complete the overall design for Navigator AI.

· Research about path finding algorithms and steering behaviours.

· If possible create a prototype Navigator AI in Python.

Midterm Evaluation (July 12)

The second stage would involve implementation of Navigator AI. Create some tests and at least one very simple demo. Implement the AI in Genie, Orc and Python.

Deliverables:

· Working version of Navigator AI. Beta quality implementation.

· Some preliminary tests.

Final Evaluation (Aug 16)

The final stage would involve thorough testing, bug-fixing, optimization and completion of documentation.

Deliverables:

· Stable version of Navigator AI.

· Demo application for showing usage of Navigator AI.

· Documentation of Navigator AI.

Progress

I am currently working on controller module in libSoy after which I would continue with Navigator AI.

Who Am I?

I am an undergraduate student at IIT Kharagpur currently studying Mathematics and Computing. I am very much interested in game engine design and game AI.

References

[1]  https://www.ohloh.net/accounts/abhishek_jha
[2]  http://www.red3d.com/cwr/steer/
[3]  http://www-cs-students.stanford.edu/~amitp/gameprog.html#paths