[Behavior]PathFinder

I'm hope you're not thinking I'm ungrateful. Quite the opposite, I'm posting this stuff for documenting what might be ironed out. :)

Meant to add this as an edit actually but it's also a seperate question. Can cells with other than square aspect be possible? Like 84x48? Until now I thought we could specify cell width and height seperately but it appears that's not the case.

First, the PF maps a grid of square cells on the whole layout. You can only set CSS (Cell's Side Size) which is applied to both width and height.

This is by "design" and I'm not sure how providing the ability to set different sizes might affect the PF in the end.

It might end up in doing another PF behavior and I'm not ready/willing to dig into that atm (I'm sorry, I don't need a PF behavior with those features). Still I'm trying to provide this "simple" (but not much flexible) behavior for now.

So with this out of the way, I've resolved the obstacle recognition in the PF. Now the PF boards is accurate with the setting of the obstacles, no matter what their size is, as long as you respect the square grid aspect in your level design.

<img src="http://dl.dropbox.com/u/36472942/construct/plugin/release/pathfinder/r75-inprogress.PNG" border="0" />

Quick image to show, the blue "mask" represents what the PF knows as "unwalkable" squares. The red sprite is the player.

You can see the first wall on the top left has a "double" mask compared to the other obstacles.

It's because of its position.

The CSS there is 32. And the wall's position happen also to be 32, meaning it sits on the edge of 2 squares.

And so it will appear as your sprite is avoiding the wall when it seems it should walk right next to it.

So if you respect the positioning of the obstacles in your level designs, it will work as intended (the rest of the blue masks).

The "big thing" that left for now is that to make the recognition work, I had to use a little trick. The square, for the PF is actually 1 pixel smaller than CSS value (31X31).

And so when you put your mouse on the position 32,32 for example, for the PF, it sets the destination point as nowhere. The destination square doesn't actualy exist.

So the algorithm freezes the whole thing.

The algorithm part of the behavior isn't code I written, so I'm uneasy going into it and hacking a solution.

SoI have already my hands full atm, and it is likely that the "new version" you report should be resolved once I'm done with the current issue.

So I'll check them as documentation and even as base to provide more examples of use of the behavior once it is done, and for that I warmly thank you, but for now please don't keep them coming ^^

Yeah to conclude another walltext, pathfinding is tricky, and this behavior won't be that flexible and constrain you in your design.

Still it will allow to cover some ground and should definetely be useful/usable up to a certain level.

Finaly it sounds as all I needed was to put things down "on paper".

Update, compatible with r75

You can download the pathfinder behavior and new (normaly fixed) examples from the first post of the topic.

Wronghands: I've just launched your two latest versions, they appeared to execute without freezing (which I was looking for).

Check the "moving with preview" example from the first post.

Kyatric

I hate to distract you but I have to tell this: I don't think the pathlist generated by the latest version is 0-based.

When you set one neighboring cell as the source and the other as target, pathlistlength returns 2 instead of 1. This makes calculating movement costs impractical if not impossible.

Sorry for the interruption.

Example

The pathlist is an array.

The length returns the number of elements (cells) in the pathlist.

Pathlist[0] is the Source, Pathlist[pathlist.length-1] is the destination.

In the case of neighbouring cells, you have 1 the start, 2 the destination. Pathlist's length = 2

Works like the array plugin.

The trickyness comes from the fact that the very first cell (pathlist[0]) is always the source coordinates.

I might indicate/make this clearer in the documentation I guess.

Also atm I'm not working on the behavior. Bug reported have been fixed, it sounds like everything should work as intended.

So if you find bugs or have troubleshooting questions, I'm here to answer, no problem.

I forgot a Wronghands ^^ (oops, check the previous page/post)

Also, thinking about it, if you want to know the movement cost in the current setting of the pathfinder, you'd need two checks.

If pathlist length = 2 => movement cost = 1

If pathlist length > 2 => movement cost = pathlist length - 2 (removing the source's cell and counting up to the last cell's index)

This will be extremely helpful to me. Thanks!

Kyatric

Sorry about the delayed response. I must thank you again. :) Your suggestion helped and I now have a simple turn based grid prototype running, can even call it a basic game. Only difference being that I had to subtract 1 from pathlist length instead of 2 when the length is over 2 but it's sorted (unless I discover a horribly glaring flaw far too late :D )

Wronghands: glad to hear.

Let me know if you find anything that doesn't work as expected or if you have any question/needs more infos.

omg !

TL;DR on the Comments so maybe this has been said before..

Heroes of Might and Magic 3 remake?

Hello again Kyatric

It has been a while and I did progress somehow on my own, thanks to your and Yann's directions of course. Now I'm trying to spawn preview sprites that indicate all the possible movement locations for the starting sprite, limited by obstacles and range. I have a crude working example of that but I'm still having several problems:

I'd like to detect collision between sprites that spawn on top of each other and kill the excess ones or even better, not spawn preview sprites at all if one already exists on target location but I've been unsuccessful to have such collision recognized by the events system. I still have an idea to add "occupied" x and y locations to an array and blacklist them from spawning but I couldn't get it working either. It has been several hours and despite the apparent simplicity of the matter it seems futile to keep trying all by myself.

Another problem is that the preview sprites are sometimes placed over obstacles. A workaround would be to keep them on different layers or z-ordering but this doesn't seem to be an intended behaviour.

The project itself has gotten a bit complicated therefore I removed the unnecessary parts and created this .capx with the bare minimums to explain the problem.

PS: I'm also open to criticisms regarding use of arrays. Thanks! :)

Wronghands: I'll try to have a look at this during the weekend.

Don't hesitate to bump the thread later if it seems I forgot.

Thank You for the 16-01-2012: Update! Pathfinding has key importance in games with enemies.

I was thinking about what my colleagues did for Nintendo NDS. Pathfinding wasn't coded into the car-racing game for (possibly) performance or limited time reasons. Spline paths were laid down along the race-tracks and enemy cars followed those invisible splines. It turned out not so bad.

So here is the idea: how reasonable is to lay down "splines" paths on the level and detect if the target is crossing one spline. Like when a soldier touches a wire-trap in a jungle war-game. Enemies would then change to that spline-track and travel down to the point where the target last touched the "wire".

I'm pondering how realistic would it be. Maybe the enemy heard something and follows the noise, goes to the last known target(player) position.

Kyatric

Shameless bump ;)

I got a question about the Plugin, what if the spot is unreachable? If it is surrounded completely by Solids for instance