Even if it isn't going to be perfect, a built-in A* function would likely be much faster than one made in VC, wouldn't it?

I'm going to need path-finding one way or another. A lot of us are. I'd be very thankful to have an internal function for it.

Since my main V3 project is mouse-based it's important that by clicking somewhere on the map the user can comfortably expect his avatar to go there, no questions asked.

It's not that easy, though, and currently I'm employing Ragecage's A* lib to do this. It's a valient effort but has some shortcomings that are all too evident, mainly involving it's accuracy.

So, I'm wondering how hard it would be for a pathfinding system to be built into V3, allowing anyone to tell an entity to go somewhere and for VERGE to calculate the relevant path (taking obstructions etc. into account) and dump it into the entity's movecode. This would be WILDLY useful, not just for me but for everyone - particularly for making AI a little more realistic.

EntityMove(ent, 'x5y6');

Sends the entity to a specific x y coord (in tiles). It ignores obstructions and does not take the shortest path. Not increadibly usefull for pathfinding tho.

Edit: Blue built a time machine to post that message. Ha!

Quote:Originally posted by RageCage

man, my A* is perfectly accurate.

That's the problem, Ragecage: it isn't. Particularly with large entities they bang into obstructions and always end up a few tiles away from where you want them. Plus, if you crank up the accuracy the speed hit while it's thinking can annoy. Still, it's the best out there.

A built-in system would be utterly brilliant. At the very least, I'd like something that got an entity to a static point on the map without them lurching around like someone after a heavy night of drinking.

[Zip: Closed the < quote > tag]

Quote:Originally posted by Zip

A* isn't designed for realtime, is the basic problem. Works well for a one-off solution (turn based map for instance), but is just plain bad if you expect 1) no visible delay, 2) path changing along the walk. However, as seen from the terrible path finding seen in even quite modern rts games, an good solution that is 'cheap' enough is not easy to find. They were programming in much faster languages than verge, as well. But... this has been on my to-look-at for a while, so I'll think about it again. Vec could of course do it faster and easier... but...

Zip

Hmm... maybe your experience with the A* algorithm is very limited. Verge, as all of us know, isn't a multi-tasking engine. Probably you're presumming it isn't the IDEAL solution becuase you have to wait until it finishes its task. To achieve such a goal you have to implement first a multi-tasking engine and then optimize the pathfinding algorithm in a way that fits in this engine.

Something else, A* resolve the problem in cubic polinomic time in the order of O((n^3)*(log(log(n))/log(n))^(1/3)), that is, is the best option for many applications.

There are many other solutions for the same problem but with different approachs, maybe you want to read books and papers:

-'New bounds on the complexity of the shortes path problem', Michael L. Fredman

-'Algorithm 97: Shortest path', Robert W. Floyd

-'A theorem on Boolean matrrices', Stephen Warshall

-'Representation of events in nerve nets and finite automata', Stephen C. Kleene and others.

How about the Dijkstra shortest path solution?

Quote:Originally posted by hellhound

man, my A* is perfectly accurate.
A* algorithm is a 50 percent heuristic implementation meaning you can't guarantee a 100% accurate solution.

I beg to differ. I have never seen a situation where it didn't find the absolute shortest path and the fact its heuristic doesnt mean its less accurate, is just means it has bias towards the most likely path.

As for the Dijkstra shortest path, it is the same algorithm as A* only the path cost of each node is based purely on heurstics instead of including the cost of total number of steps, corners, etc. You can actually use my verge A* library and transform it into Dijkstra by changing a couple values I noted in the readme. It finds the path much quicker than A* but still too slow for verge. Although I'm sure there's some multi-process type things you could do to make it seem fast enough.

Push me all you want I am not moving because you said so its just because I felt like it.