[Pogamut-list] override

[jakub.gemrot]

Re: override

Author: jakub.gemrot

Hi Jeremy!

The AStar algorithm is written as general as possible. I was inspired by Higgins's paper published in AI Gaming Wisdom (1 or 2, don't remember correctly). 

The trick of AStar algorithm is that you may use not only the found path but also a list of open / closed path nodes - I'm sorry, I don't want to offend you, but do you understand completely the AStar algorithm? I believe this knowledge is needed to successfuly use the Pogamut's implementation.

Basicly you have to implement two classes (two interfaces).

1) AStarMap
 ... simple interface that contains two methods that suffice to provide complete infomation about the search space for the AStar algorithm

  /**
   * Should return the distance from nodeFrom to nodeTo
   * You can be sure that nodeTo is among the neighbours of nodeFrom.
   * @param nodeFrom
   * @param nodeTo
   * @return cost of an edge
   */
  public int getEdgeCost(Object nodeFrom, Object nodeTo);
  	
  /**
   * This should return a collection of nodes which are connected to this one.
   */
  public Collection getNodeNeighbours(Object node);

Note that this object should be used as a plain map only - it should not be bot specific and should be reusable for many bots at once.

2) in contrast, AStarGoal interface should be bot/goal specific - it describes the target node tha AStar sould search for and contains two methods that may limit the search space.

Firstly, the goal node is specified via
  /**
   * Returns true, if we've reached the goal ... e.g. actualNode
   * is node we were trying to get to
   * if this function never returns true, A* will run until
   * all nodes are evaluated
   * @param actualNode
   */
  public boolean isGoalReached(Object actualNode);

Secondly, the search space may be altered by:
  /**
   * Returns true if A* can use this node (e.g. to step on this type of floor)
   * You can use it to forbid some specific nodes	  
   */
  public boolean isNodeOpened(Object node); 
  
  /**
   * Returns extra cost to add to value when trying to go
   * nodeFrom to nodeTo ... of course it can depends only on nodeTo 
   * (some special kind of a floor for instance)
   * 
   * Don't worry about the edge cost to become negative, A* ensures that
   * that the least cost is 0 (Algorithm can't work over graphs with negative
   * costs.)
   * 
   * @return extra cost of edge for nodeFrom -> nodeTo
   */
  public int getExtraCost(Object nodeFrom, Object nodeTo);

Additionally it contains method setOpenList and setCloseList that could be examined after the AStar terminated.

Finally, the AStar is used by instantiating AStar object with AStarMap and AStarGoal implementations, start node and limit on the number of iterations the AStar is allowed to do.

Are the things more clear now? I'm not sure whether I haven't just repeated the javadoc of the AStar, if you have any other doubts, feel free to ask!

Cheers, Jakub