Special

Introducing the “Welcome to Xojo” Bundle!

New to Xojo and looking for guidance? We've put together a terrific bundle to welcome you! Xojo Bundle

This bundle includes six back issues of the magazine -- all of year 21 in printed book and digital formats -- plus a one-year subscription (beginning with 22.1) so you'll be learning all about Xojo for the next year. It's the perfect way to get started programming with Xojo. And you save as much as $35 over the non-bundle price!

This offer is only available for a limited time as supplies are limited, so hurry today and order this special bundle before the offer goes away!

Article Preview


Buy Now

Issue 1.5

COLUMN

Path-Finding

Issue: 1.5 (April/May 2003)
Author: Joe Strout
Author Bio: Joe Strout once got lost on his way to work at REAL Software, and wished he had a path-finding algorithm handy.
Article Description: No description available.
Article Length (in bytes): 28,587
Starting Page Number: 15
Article Number: 1510
Resource File(s):

Download Icon 1510.zip Updated: 2013-03-11 19:07:56

Related Link(s): None

Excerpt of article text...

Imagine you're in a dense forest, tired and hungry from a long day of hiking. Most of the underbrush is impassable, so you're forced to stick to the trails. All you want is to get back to the lodge as quickly as possible. Fortunately, you have a trail map. So it's no problem: you simply look at the map, identify the shortest route, and off you go.

But that's because you're human. We're very good at problems like this; while you may not identify the absolute shortest route, you'll identify a very short one, without spending hours considering all the possibilities.

Computers, on the other hand, have no such natural ability. Yet it's quite likely that sooner or later you'll have to program a computer to solve this exact problem, or one very much like it. These path-finding problems turn up in nearly every modern type of computer game, whether it's finding a route through a deadly minefield or simply navigating from one room to another. If computer games aren't your thing, keep reading anyway; it turns out that a great variety of other problems, which seem quite dissimilar on the surface, can be addressed with the very same techniques.

General Approach

In general terms, a problem consists of a set of states, with operators that move from one state to another. For path-finding in particular, the state is simply what location you're in. In this article, we'll be searching for a path on a rectangular grid of cells which may be either passable or unpassable; each cell on the grid represents a potential state of the problem. We can represent any state with the row and column numbers of that cell.

...End of Excerpt. Please purchase the magazine to read the full article.