Friday, December 30, 2011

Bug in route finding

There is still a minor bug in my route finding algorithm. It lies in the reduction sub-algorithm. Seems like my strategy to select vertices for elimination wasn't perfect after all.

Path reduction works

The removal of waypoints which can be substituted by direct lines also works:

Thursday, December 22, 2011

Dijkstra implemented successfully


Now I need to implement my path flattening algorithm which removes vertices from the path when the vertices before and after it have a direct line of sigh.

Map partitioning with walk graph

Everything went better than expected:

Now I just need to implement Dijkstra's Algorithm, clean up my code a bit, copy it into my server project and remove everything I only needed for the visualization.
Done!
1 Pics
1 loaded
0 failed

Wednesday, December 21, 2011

New map partitioning algorithm

Now that's more what I wanted to see:

This new algorithm doesn't start in the upper left corner of the map but in the center instead. It expands the inner rectangle in all four directions simultaneously until it hits a different tile or the edge. Then it separates the uncovered area into four rectangles and repeats the process with those.
Done!
1 Pics
1 loaded
0 failed
Done!
1 Pics
1 loaded
0 failed

My Map partitioning algorithm works - but not as good as expected

I wrote a little Java GUI application to test my map partitioning algorithm. This is the result:

While the results of the algorithm are formally correct - the whole map is separated into rectangles which are either filled or not filled - the result is not as good as I expected. While it looks well in the left part of the map, the partitions get flatter and flatter the further you get to the right until they are all only one unit high stripes. I would prefer a more uniform distribution of large and small rectangles over the whole map. I will see if I can come up with a better algorithm.
Done!
1 Pics
1 loaded
0 failed

Saturday, December 17, 2011

Milestone 4 reached!

Players can now walk around and kill monsters.

Attack range is limited, moving cancels attacking and vice versa.

Now it's time for Milestone 5: implementing collision tiles. I wonder if I skip the intermediary step of having no route-finding and go right to implementing my map partitioning and pathfinding algorithm. I want to implement that sooner or later, and I don't think that there would be any code of the intermediate solution left which would still be required.

Sunday, December 11, 2011

Client-sided code for attacking

The user can now click on monsters to attack them, and then sees little red numbers floating out of them when the server reports damage. Now I have the visual feedback necessary to implement more sophisticated combat logic in the server.
Done!
1 Pics
1 loaded
0 failed
Done!
1 Pics
1 loaded
0 failed