Bay 12 Games Forum

Good thing too. If you have 2000 stones, its trivial to find a close one but not so trivial to check all 2000 for the shortest path. We talked about cool ways to address this a year ago or so in a different thread but a discussion of graphs is a little off topic in a thread about pathfinding. I'll just let you guys have fun and not troll this too much hehe.

I know why DF just checks the distance and not calculates the actual path and I've read that thread around the time when it was posted
I just want to help Niseg to get his simulator working nicely.

Sigh... i tried to make it clear to you, Niseg:
You can not use the Manhattan distance heuristic when you can move diagonally!

A heuristic calculates the approximate distance from the current point to the destination. You can not chose a heuristic, that overestimates the remaining distance; that means the result of the heuristic has to be less or equal to the real number of remaining steps. If you choose a heuristic that overestimates the cost, you can't be sure if you get an optimal solution / the shortest path.
For the Manhattan heuristic the distance for a diagonal move is 2: 1 to the side and 1 up/down, while the distance for a horizontal/vertical move is 1. It doesn't know that you can also move diagonally. So if the destination would be 10 tiles south-west of the start, the heuristic would calculate the cost 20 (10 steps south, 10 steps west), while the real distance would be 10 (10 steps south-west).

I can show you an example where you can see the problem:
http://niseg.0adz.com/test_maze.html?maze=v02AUAUAQETEwAAAAAAAAAAAAAAAAAAAAAAAAP_wAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
Here the Manhattan distance chooses to go diagonally towards the wall, then straight east to the end and then straight south to the destination. The heuristic doesn't know, that it can also move diagonally so it chooses the shortest way for only vertical/horizontal movement.
When you choose the vector heuristic, it correctly calculates the shortest path, by moving diagonally and left of the wall.

And i know that the sqrt(dx² + dy²) is harder to calculate, just use the other heuristic i recommended: max(dx, dy)

The A* code looked fine, but i found something you can change:
new_node.g = current_node.g + Math.floor(Math.sqrt(Math.pow(new_node.x-current_node.x, 2)+Math.pow(new_node.y-current_node.y, 2)));Because you always only take one step in any direction and the cost for each step is currently always 1 you should change it to:
new_node.g = current_node.g + 1;And when you include traffic zones you can just change it to current_node.g + new_node.traffic or whatever.


But the problem was indeed your heuristic. The function dx²+dy² always overestimates the distance to the destination, which is not allowed. It even says so in the comments. So sqrt(dx²+dy²) should also work and give the shortest way, also it should always try to move towards the destination diagonally and make zigzag-movement, but as both diagonal and straight movement have the same cost, it doesn't matter for the overall length of the path.
The Manhattan heuristic should also NOT work, because it also overestimates the cost, because it doesn't include diagonal movement, which would be two straight moves for Manhattan.
Another heuristic you could use would be min(dx, dy): because you can move diagonally with the same cost as straight movement, only the longest distance of x and y defines the overall distance.
The code for that would be Math.min(Math.abs(current_node.x - destination.x), Math.abs(current_node.y - destination.y))

Edit:
I forgot to add this, i found a nice java applet for the comparison of different search algorithms. It is in German, but you should be able to use it without problems, i couldn't find any other with the amount of features it has. http://www.stefan-baur.de/cs.web.mashup.pathfinding.html
Sadly you can only draw obstacles with a 3x3 brush, but it doesn't really change anything. Something nice about it is that it also shows all the nodes visited and not just the final path.

From what i can see is that you are not using the A* algorithm (which is optimal, it always finds the shortest route), you a simple greedy algorithm that chooses the next node with the shortest distance to the target. The A* algorithm also adds the distance from the starting node (the distance traveled) to the cost of the next move.

Quote from: Vince on August 15, 2010, 06:14:08 am

Absolutely beautiful!
A shame, that trees don't have the correct size in DF to begin with.
Hm... Maybe we could do the same "semi-multitile" thing for trees, too?
So that the "tree tile" from Vanilla DF just represents the trunk and we display a 2x3 or something tree at that place?

Shame that it wont be possible to make trees this way...

Spoiler (click to show/hide)

This is possible. You can make something like 24x24 pixel sized trees, expand the tile to 36x36 pixels with the tree remaining in the upper left corner and then add the shadow in the lower right corner. Then you move the tile so the trunk is in the middle of the tile (-3 pixels in x- and y-direction) and the shadow is on the lower right of the tree. You can even vary the x- and y-movement by a random amount like +-4 pixels so multiple trees look nicely next to each other. And you have to make sure that the tiles are rendered from top left to bottom right, so other trees are placed above the shadow of the ones on the left/above.

I could make a little sketch of what i mean if it is too complicated, but i am lacking the motivation

Quote from: pugi on August 11, 2010, 03:57:16 am

Don't trust the wiki page for the tile usage that much, the O is also used for single pieces of constructed/smoothed walls and the ends of those. I guess there are a few more things missing.

Best would be if someone would build every workshop/building/construction and write down what tile is really used for which building and then update the wiki.

Sounds great! *pats you on the back and hands you the proper tools to do it* 

I would, but i am currently at work

I think the ground tiles should be brightened up a bit, looks fine otherwise

I still don't like the constantly howling wolves