Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[jseah]

Without the heuristic, it's a breadth-first search, which does guarantee you the closest item and a path to it, but degenerates very quickly when the item is far away.

The interesting thing is, when you use the heuristic and find an item, you still need to path to it. 

Since the pathing algorithm is an A* floodfill, that kinda defeats the point no?
The A* floodfill doesn't need a target point (if you check from every edge instead of preferring a direction).  It spreads outward labeling every square with a distance from the origin square.  If you scan the lowest cost first, you are garuanteed to hit the closest item.  (or scan the whole map if there are no items)

Of course, it would be alot easier if there were a couple of checks:
1. We check each item if there's less than (a number based on map size) qualifying items from the stocks screen
2. If there's more than that, we breadth-first search (a number of squares based on map size and number of items) then swap to the heuristic if we can't find any. 

Of course, this would mean placing workshops next to stockpiles makes the game run faster, but well...

EDIT:
Actually, never mind, I see your point. 
A* breadth first gets crazy at long distances. 

[Hammurabi]

You might be able to start with the breadth-first search and give up if you don't find anything within 5 or 10 steps, reverting to the old method. That actually sort of makes sense in that a creature should be able to figure out the truly closest item within a short distance of themselves, but will maybe make the wrong decision for stuff further away.

Basically a workshop looks for the closest item using Manhattan xyz distance, ignoring walls.  This is why it can pick an item on just above or below on the next z-level, yet have to walk halfway across the map.  The current implementation could either:

• Iterate thru each item to find the closest (dx+dy+dz).  This is very fast for a small number of items, no matter how far away.
• Check each tile in an expanding radius until one is found.  This would be very fast no matter how many items, if there was at least one item relatively close to the workshop.

Your breadth-first is similar to the expanding radius above, but will always find the closest item per walking distance, as it won't ignore walls.  And it will also return the path for the item for free.  Having it bail out after so many steps is a great optimization.

[tps12]

Another note is that a breadth-first item search would require constant-time access to the items at a given location. If that doesn't already exist (it's not part of the regular map data structure) then there would be overhead involved in maintaining it.