Path finding codes
I always find it interesting to present an algorithm with graphical illustrations. Below are some path-finding algorithms in GIF format:
The typical A-Star algorithm is not very suitable on a feature phone, because you must do with the sorting in the open and close tables. When the CPU frequency is very low (about 100MHz), everything must be done in the fastest way. On the ARM platform, if you take other dependencies into account (limited memory, time for other codes and effiency of virtual machine), A-Star still seemed slow in game, even under optimization with binary heaps. The quickest way with an acceptable outcome which I found at last is similiar to the way of "go along the walls", however, key waypoints are integrated, and following optimization strategies are used:
1.Use memory pools to avoid too much malloc() and free(). Memory allocation needs a lot of time, especially on mobile devices. Programmers should be smart to use them in real time algorithms.
2.Limit path finding steps. For example, if the algorithm doesn't return any result in 32 rounds (that means the units cannot reach their destination in 32 steps), then just stop the present path-finding task to start the next one, and warn the player. This is to avoid those rare yet possible worst situations that may block the task queue.
3.Use a find-and-follow strategy. That means when player selects multiple units and orders them to move toward the same place, Only one unit's path finding will be done, and other units will follow his route.