Simple brute-force AI-pathfinding?

[Musashimaru]

I'm in need of a piece of VB code which is able to calculate the shortest path between 2 points on a grid.

A good and easy way would be to have 8 paths go one step from the starting point in all directions. Next each path should detect which points next to it are not yet 'explored' and should then continue in those directions, etc. until it has come across the target. This should be a good way to get around obstacles.

Does anybody know where I can get a small program doing something like this? It would really come in handy.

Thanks!

Musashimaru

[kedaman]

No idea where you can get that code, and this algoritm may be very hard to code. Just if you want to start making it I could give you some advice, you should make a dynamic 2d array (or 1d udt) for position of each coordinate on the path. You should first make a path searching algoritm that first searches a way to your goal by going towards it, if you hit any obstacles just split it up in two directions and start call the procedure from there. After finding the goal you may need an algoritm to make that path as short as possible by finding short ways.

[Illuminator]

As for path finding algorithms look up Prim' Medthed, Euler Paths, and Dykstra's Method.

Prims Method ->Shortest Spanning Tree (shortest way to connect all nodes)

Dyksta's(I'm not sure if that how you spell it) ->Shortest path between any two points on a graph.

Eulers Method-> Determine whether a graph can be traversed using all acrs between nodes...

There are other topics about path finiding too but the above are the only ones I know.

[kedaman]

Do you have any links?

[Musashimaru]

Thanks for your replies!

I know about the Dijkstra (correct spelling) algorithm, but I'm really new at VB, so I don't know how to do it quickly in VB.

I hope somebody knows where to get something like this. I have already tried planet-source-code.com, but all they have are three very crappy path-finding thingies. :-(

[Musashimaru]

I'm not posting this reply just to get at the top of the forum and keep people looking to my problem, of course not ;-)

[Illuminator]

Before I give you a detailed explanantion and yes..even a code section I would like to know underwhat circumstanses your pathfinding is taking place. Dijkstra's Algorithm is very limited and is best for calculating shortest distances on maps and such where there are set nodes, arcs and arc distances.

[Musashimaru]

Thanks!

It will be used on a grid of about 100 by 100 tiles. There will be different tile types each with their own movement cost. It doesn't need to be fast. It doesn't need to be fast AT ALL, well, 1/10th of a second is a lot of CPU cycles isn't it ;-)

Thanks again! Looking forward to your reply

[Illuminator]

Here is the pseudocode (must be conveterd for VB use) I found...it helps to have a bit of set theory and graph theory. The code will have to be altered for your purpose however


'Variables
A 'Adjacency matrix
x,y 'x and y areyour start and finish nodes

IN 'set of nodes whose shortest path from x is known
z, p 'temporary nodes
d 'array of integers - keeps the distance for x
s 'array of nodes - list of shortest path nodes
OldDistance 'comparative distance

'Iniate set IN and arrays d and s
IN = {x}
d[x] = 0

for (all nodes z not in IN)
d[z] = A[x,z]
s[z] = x
next

'Process nodes into IN
While (y not in IN) do
'add minimal distance node not in IN
P = node z not in IN with minimum d[z]
IN = IN + {p}

'recompute minimum-distance node not in IN
for (all nodes z not in IN)
OldDistance = d[z]
d[z] = min(d[z], d[p] + A[p,z])
if (d[z] <> OldDistance then
s[z] = p
end if
next
end while

'now all the nodes in IN are the nodes that form the
'shortest path



This code came from "Mathematical Structures For Computer Science, fourth edition" written by Judith L. Gersting

Adapting this code for your convetnion will require some serious thouhgt...for example the thought of making a full adjacency matrix is crazy (A 100 x 100 map turns into a 10000 x 10000 adjacency matrix) best just make a matrix that only contains the nodes and the nodes they point to
this will still lead a large matrix but more managable for speed. There are other considerations too, but I cant think of any other main ones now...If I get something working however I will let you know.

[SteveCRM]

I never tried to make this, but couldn't you just do something like this?



Dim GoToX as Integer
Dim GoToY as Integer
GoToX = 'whatever, but along the X axis
GoToY = 'whatever, but along the Y axis
If Player.x > GoToX then Player.x = Player.x - 1
If Player.x < GoToX Then Player.x = Player.x + 1
If Player.y > GoToX then Player.y = Player.x - 1
If Player.y < GoToX Then Player.y = Player.x + 1


This won't go around anything in its way though.

Yeah! This was my 400th post! :)

[Illuminator]

For conventional purposes that would work..you could then elaborate on that by writting code to handle the case when its path is blocked by exploring unexplored areas then occasionally run that base move routine again.

I had a game where the user would draw a maze and a robot would find its way through..I lost the code :(

This problem here is slightly different because we are dealing with the fact that difference parts of the map affect movement speeds and thus a straigh line might not always be fastest path.

[Apollo]

You could do the easiest thing and make the enemy to change directions randomly. I always found that very interesting. An unpredictable enemy is a scary one... just like in The Legend of Zelda... a room filled with 7 of those blue knights just randomly dancing around.

I also thought that that whole if yourtop > their.top then their.top = their.top + whatever is a pretty good idea. Especially for say... something flying? And in order to make it seem a little more realistic just make the time between direction switching a little greater.

Why would anyone want to program AI.... *shudders*

[kedaman]

Can anyone convert Illuminators code into VB? Would be great.

[Illuminator]

I translated the code!!!! How ever it was quite tedious and only works with linear graphs (It is also very long). It will find the fastest path if the path is limited to hallways however if you try to cross a room it takes a very obscure and non efficient method to do so. Also it is very slow.

I am now trying to take a map and calculate efficent nodes. Then these nodes will act a way points for the search routine and hopefully cause the code to be more efficient

[Illuminator]

Ok I have a working program now (and it is fast :)). You draw a maze (35 x 25) tiles using 5 different tiles which represent the time to cross that tile. Next you set a start and end point on the maze. From here I developed an algorithm for finding nodes(intersections) on the map. Finally I implement Dijkstra's algorithm to find the order in which the nodes must be traversed to reach the finish in the fastest manner. A red dot will then walk through the fastest path. The code is a bit to long to post here however.

Again it doesnt like open areas because my node creation algorithm looks for intersections.

[kedaman]

oh God, this must be good, Illuminator, can you send me that code? And you would do me a great favour!

I have like mountains and slowing stuff in my game so that would be like just perfect!

[SteveCRM]

Send that to me too please :) --> SteveCRM@altavista.com

[Illuminator]

Sorry about the delay in sending that file..let me know if you have any troubles or questions about the code.

[Musashimaru]

Could you send me that code too, please? Thanks!

[Illuminator]

Ok, Post problems/questiosn here so that if anyone else has them they can find possible solutions posted.

[SteveCRM]

It froze when i did it :(

[SteveCRM]

Oooooooo! It works now! That Works Excellent!

[Illuminator]

I'm glad you like it...I am now trying to get the routine to recognize open areas and cross them effectively. So you could simulate mountians/hills/water and then the routine will find an effective way around/through/over these obstacles to the destination with relative speed.