Irrlicht pathfinding class available

[CZestmyr]

Hi, I created my own A* Pathfinding class, which worked well. Later I wanted to implement 3D pathfinding in Irrlicht, which also worked well. But because I used my own linked list class in the PF Class, I decided to remake the PF Class so that it would use Irrlicht classes only. And that's where a problem arose.

Everything compiles ok, the program runs well, but when I want to find a path, something goes wrong and the program crashes down.

By printing data out to a log file, I figured out, that the line, causing the trouble is probably this line:

Code: Select all

extendedList.push_front(extended);

Extended list is an object of type irr::core::list<path>,
where path is nothing more than irr::core::list<something> with a few functions.

If anyone had a guess, what could cause the troubles here, I would appreciate it. Just tell me, if you need the code posted or something.

My guess was, that core::list<T> doesn't have any copy constructor, thus pushing it back to the extendedList and later on deleting the old object would cause a problem, but I already tried to create a copy constructor for my path class, which didn't help though.

[FlyHigh]

I'll go with a guess and say:

"Does your path class have an assignment operator? (and does it use pointers?)" When the item gets copied it might only be a shallow copy...

Just a guess

[etcaptor]

Extended list is an object of type irr::core::list<path>,
where path is nothing more than irr::core::list<something> with a few functions.

Have you tryed something like:

Extended list is an object of type irr::core::list<path*>,
where path is nothing more than irr::core::list<something>

[CZestmyr]

2 FlyHigh:

Yes, I created the assignment operator with the copy constructor.

The path class doesn't include anything more than inherited members of core::list<T> and a few functions, which can't cause any problem.

By the way: my copy constructor and assignment operator do this:

They call clear() to initiate the current list,
then they iterate through the other list using the list iterators,
and they push_back each element into current list.

Don't see a problem there.

Hmm... I may have to post the code...

[CZestmyr]

2 etcaptor: Good idea, but I have to copy the list, that's part of the pathfinding algorithm.

[CZestmyr]

Hurray! I managed to solve the problem. It was something with the core::list<T> Iterators and their functions. Some function using these iterators didn't work properly when the iterator was end().

Anyway, the class is finally done and you can download it here:
http://www.czestmyr.wz.cz/other/irrpathfind.zip

Use it like this:

Code: Select all

// Create the pathfinding net
Network* pathnet = new Network(driver, device->getTimer());

// Add a few nodes
pathnet->addNode(vector3df (0.0f,0.0f,0.0f));
pathnet->addNode(vector3df (20.0f,0.0f,0.0f));
etc...

// Connect two nodes by selecting two of them at a time
// You don't have to enter the precise coordinates, the nearest node will
// be selected.
pathnet->selectNode(vector3df (0.0f,0.0f,0.0f));
pathnet->selectNode(vector3df (20.0f,0.0f,0.0f));
etc...

// Finally, you can find path between any of the nodes by calling
// the findPath method
pathnet->findPath(vector3df (0.0f,0.0f,0.0f));
pathnet->findPath(vector3df (20.0f,0.0f,0.0f));

// The path can now be extracted from the pathnet
path myPath = pathnet->pathSegments;

// Path class is just a child of the irrlicht list class, this means
// that you can iterate through it with the list iterators
list<PathNode*>::Iterator iter = myPath.begin();
while (iter != myPath.end())
{
    // Dereferencing the iterator gets you the path node pointer
    // This points to the node in the net
    // You can for example get the node's position and do
    // something useful with it
    vector3df savePositionHere = (*iter)->position;
    iter++;
}

For example, I made a pathfinding bot animator, which is an ordinary scene node animator. It moves the node towards the player, when he is in sight and not behind any obstacle and when the player is no more visible, the animator finds a path from the current position of its node to the last position, where the player has been seen. Then it moves its node along this path, which looks like the node looking for the player.

If you create something interesting with my class, let me know, I'd be glad to see it.

P.S. And if you find a bug, write to me as well, but I hope there won't be any bigger bug.

[Electron]

hmm. I didnt take a long look at your code, but I'm curious what algorithm you're using. It didn't appear to be A*, though I only took a quick glance

[Electron]

hmm. I didnt take a long look at your code, but I'm curious what algorithm you're using. It didn't appear to be A*, though I only took a quick glance

[Electron]

hmm. I didnt take a long look at your code, but I'm curious what algorithm you're using. It didn't appear to be A*, though I only took a quick glance

[CZestmyr]

2 Electron: The forum is buggy in the last few days, isn't it?

The algorithm really is A* (or a very near equivalent), because it's main features are path measuring, sorting explored paths by distance and simple heuristics (exploring more promising directions first). The only thing that is not entirely A* is that when I find out, that a node has already been reached, no matter after which distance, I discard the current path, which is not the case of A*, which leaves the shorter path. But it would be very time consuming to search for the path containing the node, so I decided to leave the algorithm as it is. Still, the paths are ordered in the list by their length.

But I'm not a pathfinding expert and may be wrong. I would be glad to learn something new.

[Electron]

hmm interesting. The reason I did not think it was A* was I saw nothing that looked like A*'s open and closed lists. Perhaps I'll take a closer look at your pathfinder when I've got some time and see how its speed compares to mine (link in my sig, Download page), which is pure A* (though uses a cheap list in addition to the open list), though it needs some significant tuning in some places, mostly the hash tables.

[buhatkj]

any word on if/when you might release this potentially-ridiculously-useful code??
*hopeful*

[FlyHigh]

Thats quite interesting, although I don't have a need for one yet it looks pretty helpful.

How is it implemented? just a standalone class? I was thinking it would be really good as a scene animator

[etcaptor]

Nice,
If you post any example project in addition, that will be great.
About idea for patfinding animator, I like it. Even was started writing of all AI for my game based on animators. My opinion is that Irrlicht animators must be enchanced a bit.
@CZestmyr, thanks for your work.

[CZestmyr]

2 etcaptor: Will post a simplified project soon, with the bot animator as well

2 Electron: Hey man! You were partially right! I read another article on the A* pathfinding recently and it really talked about the open and close lists. I found out that my algo does the work of the lists by discarding already visited nodes. Nevertheless, I wanted to try a different attitude - searching for the path by parenting the pathnodes instead of copying every extended path, which was in my opinion very memory and time-consuming. So, I re-coded my pathfinding class to suite these new requests and it proved to be quicker than the original one. The last lines from the log files of those two classes (old one and new one) speak for themselves:

Old algorithm: Pathfinding took 47 timer ticks (milliseconds).
New algorithm: Pathfinding took 14 timer ticks (milliseconds).

What's interresting: both classes found the same paths and had exactly the same number of iteration and went through the same nodes.

Anyway: Everyone can download the improved pathfinding class here:
http://www.czestmyr.wz.cz/other/irrpathfind.zip