Tell me more ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.
up vote 11 down vote favorite

I'm interested to know if heuristic-based path-finding algorithms such as A* have any real world practical use outside the realm of game development.

Are there any other fields of software engineering that employ path-finding algorithms, perhaps in a completely different or unconventional way, or is it by the nature of those algorithms and their design that they ultimately see very limited use in other areas?

share|improve this question
1  
AFAIK A* is one possible algorithm used in routing - i.e the basis for the internet. I'm not sure if it is the algorithm used though. – Max Apr 21 '12 at 17:53
3  
Note that such algorithms don't find a path on some specific kind of map of a video game world, they find paths in graphs. Graphs are pretty much the single most flexible data structure out there. You wouldn't believe how many things can be modelled as graphs. (Linked lists and trees are special cases of graphs, by the way.) – delnan Apr 21 '12 at 18:07
An example that amazed me, although it's still game development: The first-person shooter F.E.A.R (with a much-lauded AI) makes good use of A* for guiding AI behaviour (rather than finding paths when the AI decides to go somewhere). The state of the world is treated as nodes, and the actions possible in that state are the transistions. After setting a target state (e.g. player_hp = 0, my_hp != 0), any path finding algorithm finds a sequence of actions that's likely to result in that target state. See Three States And A Plan. – delnan Apr 21 '12 at 18:22
How would you define a "game" in software terms? If you think about it, video games tend to mimic the real world, which means that the real systems out there controlling things need to implement exactly the same algorithms. E.g. financial trading with fake money could be turned into a "game", and the software which controls a flight simulator would have to handle the same kinds of complexities as a real aircraft. The only difference between a 'game' and everything else is that losing the game doesn't end up with something bad happening in the real world. – Ben C Apr 21 '12 at 23:16
@BenC: And not even that is entirely true; losing games can have real-world consequences; the simplest example being that losing a game in an arcade causes the machine to gobble up your quarters at an accelerated rate. – Williham Totland Apr 22 '12 at 11:02

7 Answers

up vote 12 down vote accepted

The most obvious example is pathfinding. (The activity from which the discipline takes its name in the first place.)

As an example, finding the shortest route through a road network (like Google Maps does), or automatically scheduling a multiple-leg trip in a public transit network (like many sites for the networks of different cities do).

It could also be used to predict resource acquisition patterns in growing fungi, migrations of animals, or designing traffic networks in the first place.

It could probably even be used to evaluate options in complex processes, although by the time you have the map you need to search for the best path, you will probably have solved your initial problem to begin with.

The essential truth one needs to remember being: Most everything can be looked on as a game, so most every game development technique can be used outside of what we normally call "games".

share|improve this answer
These algorithms are also used by the military for cross country mobility, where they have to include the hardness, slope, and width of the paths. Package delivery companies use them to minimize left turns. Rescue squads use them for routing of emergency vehicles. – mhoran_psprep Apr 21 '12 at 18:39
up vote 5 down vote

I used a path finding algorithm in a web application (A* in fact) to create a route for picking items from a large warehouse. If the optimal route is not calculated at the start people doing the picking could take twice as long to get a list of stuff. Over time this is a massive saving on time and effort.

share|improve this answer
up vote 3 down vote

Routing in IC design is a kind of pathfinding.

share|improve this answer
..and PC boards. – Jerry Coffin Apr 22 '12 at 4:30
up vote 2 down vote

Not sure exactly which algorithm is used, but every time you establish an Internet connection to another server, the connection needs to find a path to it among an enormous, worldwide graph of interconnected hubs. That's pretty real-world IMO.

(To keep the graph search from becoming huge, the Internet uses a tiered system. At the top are the backbone connections, and at the bottom are you and me, and in between are various sub-networks. So you don't have to pathfind across the entire worldwide Internet to find a server that's located, say, in the next state. You just walk up the tiers until you find a match, and do pathfinding within each sub-network to get your route.)

share|improve this answer
up vote 2 down vote

I tinkered with a recommendations engine and by setting up a graph based on peoples likes, I was able to determine what other products they might be interested in by finding shortest route to other products.

share|improve this answer
up vote 1 down vote

I have used time constrained simulated annealing to solve a path-finding problem in touch panel manufacturing. Every millisecond we could shave from the cycle time of the laser etching of each panel would increase the throughput, utilisation and thus profitability of the machine, so I put a lot of effort into minimising dead time (non scribing paths) between scribing paths (which obviously couldn't be optimised away).

I used a time-bounded algorithm to get around the NP hardness of the problem, as we couldn't afford the risk that optimisation calculation might take longer than the time saved by the more optimum path.

While the machine was moving the panel from the final alignment fiducial to the closest scannable tile I had the time to run some simulations. The algorithm almost never ran to completion within the few hundred milliseconds of the move, but almost always returned a better scribe path than any of the simple, non adaptive models we had always used before (such as a spiral or snake paths).

share|improve this answer
up vote 1 down vote

This algorithm, or something like it is used by logistics software which plans the optimised route for couriers and delivery drivers worldwide, every day.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.