I have started working on Sound, as Kostatus has gracefully taken over the work of melee code. In the process of doing so, I simplified the Node class originally used by A* and derived an AStarNode subclass from it. This makes the Node class useful as a base for building other more creature senses, should they become necessary.

I have revisited my originally flawed implementation of A* and made some changes to it to reduce memory footprint. The original design was a lazy quick hack. Now I am happy to say that the memory usage has been reduced by a factor of 2/3. The reason why I favor memory footprint over speed is because the in-dev WoT as it is (with my configuration) requires 35MB to run, including all the overhead of the Java VM. I don’t want to add any extra fat to that. Normal creature movement uses ~3% of my (1.4 GHz) CPU cycle. So that should be as good as it can get. Besides, the memory saving will become even more significant when the pathfinding algorithms (A*, Dijkstra) are used on bigger maps; so the little loss on CPU cycles is not too bad.

The basic framework for sound has been implemented. I’m a bit too tired to test it out now, so I will probably do it tomorrow or later in the week.

by Atholas

I wasn’t so happy with the original AI movement that the nomial creature does; it was implemented quickly to check for the correctness of our A* implementation. So, I started adding in features that make the AI movement more “realistic”. Having implemented all that, I wasn’t too happy with the way A* break ties — it doesn’t do it at all. I have experitmented with different method of tie-breaking and other people’s idea, and eventually the tie-breaking problem is partially solved, but I am left with some odd cases where the tie-breaking method doesn’t work. In the end, I have to tweak the A* algorithm even more to deal with these cases. Contrasting the current pathfinding algorithm with the one in the old C++ WoT 0.0.2 gamma 1 release (we also had a 0.0.3, but that was an internal release), the current A* implementation is definitely much more mature and also more fun to play around with.

As far as pathfinding goes, there is very little left to do. Most of the AI basic movement features I have wanted are implemented, and the ones that I have in mind are gonig to get implemented soon. Thanks to Kostatus and our new co-developer, there isn’t so much tension in rolling out releases. So, I am left with a lot of time to pursue new ideas and polish the existing ones.

AI movement is affected by a lot of factors, and (shrotest-)pathfinding is only one of them. So just movement AI alone, there is much left to do. I am going to start implementing AI features that Kostatus and I wish to see in the mid-Feb release (I will temporarily codename it Rockie), in particular the next feature I will implement is sound-driven movement. We don’t have enough infrastructure as yet to implement the other AI I have planned, so I will leave them out for now. I will most likely have to reassign some of the basic attack codes to Kostatus ot implement myself a bit later.

by Atholas

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

I have reviewed Shuruppak today, as a playable game it is… no good for various reasons, but it does have some very interesting features. Even though I have heard of them before I had always assumed that things like some of these would be just way too slow and bring the game to a crippling speed, but Shuruppak seems to have no problems (even though I tested it on a 3GHz, I doubt that the developer would release something that would crawl on even a 500MHz).

• Sound. Whenever you do an action it makes a sound, some actions make louder sounds than others. For example walking or equipping a hat would make virtually no sound, but changing heavy chainmail armour would make a lot of sound. Sound is propagated through the dungeon using Dijkstra. Just a reminder - if not terminated early, Dijkstra traces the shortest path from a starting node to every other node on the graph (map in this case, but same principle). So actually the algorithm is only performed once! And if you are in need of a fight there is a Yell function, needless to say, it causes a lot of sound.
• Sight. There is some sort of a concealment raiting which determines how easy you are to spot by sight. Standing in the shadows increases this raiting. ie. If you are closer to the wall there is more shadow, hence you’re more concecaled.
• So once a creature has detected the PC (by sound, by sight, or maybe some other means), A* is used to find the shortest path from the creature to the PC. A* is considerably faster than Dijkstra when there are no edge weighings on the graph, and when you just need to trace from point A to point B rather than from point A to every other point.

(I got most of this info from the game itself as well as their tech info pages.)

So I think Sound is a feasible one, and the option of yelling is pretty cool.