Having found a post in the google group about multiple proposals to one
organisation being ok, I have submitted my second proposal. I hope this is
not too much of a nuisance for the CS team.
My final proposal is listed below and I would greatly appreciate any final
comments anyone may have. I would also like to take this time to quickly
say thank you to everyone who has helped in this discussion and I
genuinely hope that this work will be able to begin soon.
Kind Regards,
Sam.
My Project Proposal.
The A* algorithm currently used within CEL for pathfinding is, despite
being an optimal solution for finding the shortest path, a slow and often
unrequried detail in pathfinding within a game environment. When used in a
game scenario it can lead to delays in responsiveness due to agents
calculating the whole route before moving and inefficiant as by the time
the full path is calculated and performed the dynamic nature of the
environment often leads to the final segments of the route never being
performed.
To fix these general faults and to overcome the performance issues of the
CEL implementation (recently discussed in the CEL mailing list) I propose
to implement a HA* algorithm. For a more detailed explanation of HA*
please see This Paper and for a nice overview please see This Description.
Also raised during my recent discussion on the CEL mailing list and in
this update within the SVN (Revision 3391) it has been noted that the
current steering implementation is still a work in progress. Currently not
all of the behaviours work correctly, the performance is bad and a more
complete implementation of Craig Reynolds' work is desired.
To solve this I first intend to work with the current cel-graph
implementation to improve the integration between steering and cel-graph.
This may also require some work within the body of CS to implement the
ability to change colliders for navigation. Once performance is
satisfactory I will look to implement the full body of behaviors presented
by Craig Reynolds.
Finally, deadlines permitting (this may need to become a personal project
after GSoC) I would like to look into the code previously worked on for
the automatic generation of navigation meshes. This would be a very useful
tool when combined with the new improved pathfinding and steering property
classes allowing for some very complex, believable and interesting AI
agents.
Taking into consideration my other commitments during the first week of
implementation my proposed timeline of deliverables is:
1. Pathfinding
1. Implement a HA* algorithm more applicable to games than the
standard A* solution
- June 21st
2. Cel-Graph
1. Improve integration with pathfinding and steering to remove
current performance issues
- July 8th
3. Steering
1. Implement all Craig Reynolds' example steering behaviors
- July 19th
2. Document all behaviors and create example/tutorial programs
- July 22nd
4. Automatic Navigation Mesh Generation
1. Collate existing work and document current faults
- July 26th
2. Begin development on improving and finalsing navigation mesh
generation tool
- Remainder of project
------------------------------------------------------------------------------
_______________________________________________
Cel-main mailing list
Cel-main@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/cel-main
