Paths

**dvadas** · May 13th, 2000, 05:56 PM

I'm writing a tile-based rpg, and I need an algorithm that finds the shortest path from one tile to another. I've been looking around for many things and all I could find was stuff written in C++ that was too complicated to read.
The only type of tiles are either walkable or non-walkable, so there are no varying speeds or anything. I just want some simple VB code that works. It doesn't have to be the fastest or the best, as long as I can use it.
Any help would be appreciated, thanks!

dvadas

**Darkwraith** · Jul 24th, 2003, 04:49 PM

A* is somewhat complex but doable.

However, if that is too complicated, you can check to see which tile you can move on that will be the closest to your target.

For example,
if ((Your character).x > (Target character.x))
' Move left
else if ((Your character).x < (Target character.x))
' Move right

if ((Your character).y > (Target character.y))
' Move down
else
' Move up

There are a few problems with this (hanging on walls) but other than that, it is a simple way of doing things.

**Electroman** · Jul 24th, 2003, 04:56 PM

Darkwraith: You fancy writing a flow blown procedure to find a path like he described?? By this I mean a procedure that would find the best way to get from one tile to another avoiding walls and avoiding hanging to walls, i say this because you seem the helping type and as you said before you bring up these threads to help others that might have similar problems

, hey it could be fun

, what you say??

Are you working on a project at the moment??

**Darkwraith** · Jul 24th, 2003, 05:03 PM

I could do the algorithm, but probably not the code.

I am working on a few projects to learn programming languages better. If it is VB, I could probably work on it, albeit it might take a few weeks (Project MagicBase is not working out to well. A respite from it would be nice.)

**Electroman** · Jul 24th, 2003, 05:23 PM

MagicBase, respite

You lost me??

If by:

If it is VB, I could probably work on it

you mean the path finding thing, he was asking for VB he said he only found C++ soruces which were no good

. if you could do the algorithm I could probably do the code.

I'm currently working on a game and its almost finished. When I say almost finished I mean the code, I have to make the levels after that which isn't gona be easy for me considering I can't draw on a PC to save my life

.

**SLH** · Jul 24th, 2003, 05:33 PM

As luck would have it, i've been doing something very similar (tile-based shortest path finding algorythm based on the A*).

I wrote it in VB, as my C++ isn't too hot, but i'd emagine it could easily be ported.

I first created the A* algorythm as it stood (no modifications - just an implimentation). My Monsters ran the algorythm each time they wanted to move. I found this to be quite CPU intensive - mainly when there was no path).

I decided to create an array, storing a direction to move in, given a source and a destination.

This means that the monster simply looked at it's position, and it's destination, and the array would give a direction to move in (based on the best possible move).

To fill the array i used the A* algorythm over and over again.

This took several minutes on a small (25x25 grid) map. Although i could save the array to a file (and did), it was still too slow.

I then decided to refine the algorythm.

I decided to calculate all the distances from the destination (for each node). Then to get a direction from a source, it's simply the direction of a node near it (with a link to it), with the shortest distance.

At present, my AI module is a bit cluttered. (failed attempts etc), but i'll try to sort it out if you like (add more comments etc).

**alkatran** · Jul 24th, 2003, 08:10 PM

Here's an example, but I strongly advise you write one yourself.

BTW: I'm slowing it down with a for-loop, and the squres 'n stuff shouldn't apppear, obviously.

Most of the unneeded code isn't tabbed, to make it easy to find.

**Darkwraith** · Jul 24th, 2003, 10:45 PM

MagicBase. My project name for a Magic: The Gathering database.

Well, it looks like a moot issue now unless you want me to create another A*, Electroman.

**Electroman** · Jul 25th, 2003, 06:03 AM

I guess your write its no a moot issue

.
What is a A* anyway, is it just the type of algorithm thats used for this??

**SLH** · Jul 25th, 2003, 06:17 AM

Originally posted by Electroman
I guess your write its no a moot issue .
What is a A* anyway, is it just the type of algorithm thats used for this??

Yes - it's a pathfinding algorythm - widely regarded as the fastest my many academics.

http://www.gameai.com/pathfinding.html

http://www.intrafoundation.com/pathfinder2d.asp

**Darkwraith** · Jul 25th, 2003, 08:16 AM

You can also try (albeit sorta old)

Real-Time Game Programming Using MS DirectX 6.0.

**SLH** · Jul 25th, 2003, 08:50 AM

you're just taking the piss now arn't you Darkwraith.

That link doesn't seem to be a link.

**Electroman** · Jul 25th, 2003, 08:57 AM

Did he mean it to be a link??

Isn't he just saying the name of the referance to add in VB??

**SLH** · Jul 25th, 2003, 09:36 AM

Originally posted by Electroman
Did he mean it to be a link?? Isn't he just saying the name of the referance to add in VB??

Oops! Quite possibly. Guess we'll just have to wait and see.

If it is a reference to add, then u'm not quite sure of it's usefulness as it is so old.

**Darkwraith** · Jul 25th, 2003, 09:46 AM

Its underlined, not a hyperlink.

It's an excellent reference in RTS design, not implementation. A section of it is dedicated to A* pathing, another to differences in design of tile based maps (rectangular, isometric, and hex)

Furhermore, it points out questions that you should ask yourself like how should economy be handled and gameplay issues.

**Electroman** · Jul 25th, 2003, 10:49 AM

Oh hang on is it a book, I've just thort this because I can't imagine a VB reference would tell you all that and he never actually said if it was a VB reference, as in .dll)

**Darkwraith** · Jul 25th, 2003, 03:09 PM

It is a book about RTS using DX 6.0 and C++.

Remember that old adage: "Give a man a fish, you feed him for a day. Teach a man to fish, you feed him for a lifetime." Well, "Give a man a coded algorithm, you help him for one programming language. Have him learn the concepts behind the code, you help him for all languages."

The code is old, but the concepts are not (especially the detailed look at A*.)

**cyborg** · Jul 25th, 2003, 07:03 PM

there is a path finding tutorial on this page: http://fox.acky.net/

Thread: Paths

Thread Tools

Display

Posting Permissions