Paths

[dvadas]

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]

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]

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 :D, hey it could be fun :), what you say??

Are you working on a project at the moment??

[Darkwraith]

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]

MagicBase, respite :confused: :confused: You lost me??

If by:If it is VB, I could probably work on ityou 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]

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]

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]

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. :D

[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?? :confused:

[SLH]

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?? :confused:

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]

You can also try (albeit sorta old)

Real-Time Game Programming Using MS DirectX 6.0.

[SLH]

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

That link doesn't seem to be a link. :rolleyes:

[Electroman]

Did he mean it to be a link?? :confused: :confused: Isn't he just saying the name of the referance to add in VB??

[SLH]

Originally posted by Electroman
Did he mean it to be a link?? :confused: :confused: 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]

:D 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]

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]

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]

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