I really should be sleeping now, but instead I am working on the A* algorithm. I have created a new package for files related to pathfinding, and I am just about finished with a preliminary design. Thankfully the Java standard library/package has a very good Collection framework, so some of the components of the implementation are done. For efficiency and naturality, I have decided to use a priority queue to implement the open list for the obvious reason (O(1)). As for the closed list of the algorithm, I am going to use a red-black tree as the underlying data structure. As it is O(log_2(n)) for adding and retrieving, it should be the best for us in this case. Thankfully Java has implemented red-black trees in the standard package, so less code writing there.

I still need to do a little bit of research on heuristic methods other than the diagonal distance method that I now have in mind to start off the class with. But since the underlying data structures are provided, I only need to implement the nodes for the algorithm and the actual algorithm itself. Looks like the Astar class might be pretty small after all. Hopefully I can get this done by tomorrow.

Time for bed before my liver breaks down.

EDIT @ Nov 17, 7:35am: updated the part regarding closed list.

by Atholas