[Behavior]PathFinder

Wronghands: Sorry for the delay.

This was a question worth of the "how do I" topic though, not specificaly related to the pathfinder behavior.

Commented capx, hopefuly this should help you.

For arrays, check the how do I FAQ, the topics listed there are pretty useful and should get you going with the use of arrays.

Schoening: In the case that the start is surrounded by obstacles, the PF will raise a "Failed to generate path" trigger, as explained and displayed in the demo/documentation in the first post.

Ok, I'm done here :D

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.

Apparently, not completely done ^^

mercy: The actual PF kinda acts like the spline method you describe.

Instead of a line though, it's cells, covering more ground at a time.

The downside is that the testing zone is the whole layout at once, cell/cell.

I may have some plans "someday" to push the developpment on the PF to allow the user to set the scan zone to optimize performances.

But it is not in a close future, I have other projects that I need to take care of first, and those projects don't require a PF as of now.

For your "spline"/"line of sight" method I'd go with events, positioning a "marker" on a regular basis (maybe not every tick, maybe something like every 0.1 seconds), and checking for collisions on the positioning (or the following tick).

Gotta use some finish state machinery here, but it should work pretty well and not require a lot of events (especialy if you use families) or performances.

I think it's reasonably doable.

Check the how do I FAQ, there are some LOS examples listed in it that might give you some leads.

My answer is maybe a bit unclear and certainly not complete.

If you want to learn more/have more feedback on this idea just post a new topic in the how do I section, you should get some more complete answers in the couple of day/weeks following the thread.

Done for now for good <img src="smileys/smiley1.gif" border="0" align="middle" />

Kyatric

Yes, more people will benefit from your solution If someone with required forum priveleges can/want to split the relevant posts to a new thread there; sorry about the extra work for whomever wants to do so. Just wasn't sure if I could post about a third party behaviour there.

As for your solution itself, I'll be examining it with a clear mind soon. I can say it's neatly and intelligently done just from the looks now. Thank you for everything you've been doing for us noobs. :)

This plugin was very easy to get started with. I like it a lot--especially the example with the smooth and stepped movement.

However, when trying to make a pacman clone, I ran into a few problems that are probably due to my ignorance. If I can get the game working reasonably well, I'd like to make an in depth C2 tutorial using it.

pathfinderPMan.capx

1) Cannot get the ghosts to start where I put them (in the "corral" in center of the board.) They keep starting at somewhere around 0,0.

2) Performance was really slow. Is this because there are 4 ghosts using the pathfinding plugin? Or is it because my obstacles are all kinds of weird sizes? (see 3)

3) I wasn't sure what you meant by saying that the obstacles had to follow the grid size we set. Do you mean the sprite dimensions have to be evenly divisible by that size, or do you mean they have to line up with the grid? Because mine don't. The pathfinding seems to work okay, but it does get slow. Is this why?

4) I created my game by modifying your path following example, but there is something in it that causes the objects to quit following the path and go back to the first point in the queue when the iteration is > self.PathFinder.getPathListLength. When I tried to rip it out, the ghosts stopped moving. How can I make them stop where they are until they start the next pathfinding loop? Possibly related, is there a way to limit/unlimit the maximum number of steps allowed in the path?

That's enough for now! Any help would be appreciated.

I wrote a Pacman game for a medical conference in ~1998 in Turbo Pascal, complete with graphics and sound effects and they liked it, especially the doctors children and I was paid. They gave as feedback the navigation being too hard, so i had to write a player-navigation-enhancer code that not only bounced off PacMan from walls 1-2 pixels but also made easier the sliding along walls. So the respected doctors didn't stuck into walls or weren't bogged down in intersections.

Checked out the Pathfinder behavior example. It is a good behavior can be used to make great games.

I may be wrong, but in your case kittiewan it seems, it isn't really suited for realtime quick checks for multiple entities. Hence: the game you presented pauses or locks for 1-2 seconds regularly.

You would be much more on track giving away Pacman X,Y coordinates to the enemy, so monsters always move in the player's direction. Put an invisible red rectangle as special trigger to each intersection. Put four yellow-rectangles in the four corners of the map.

Then:

If monster is colliding with red-rectangle (in a road-intersection)

change monster direction by re-targeting it to Random(Yellow_rectangle_coordinate[1-4])

So if a monster was moving toward PacMan fleeing south, at the intersection it can change Random direction to North-East. Until the next intersection, where it again decides where to go.

Give monsters sight:

if Pacman is close = Monster_target_ = PacMan X,Y

Shucks. I was afraid the performance bottleneck was the pathfinding. I still really like the pathfinder plugin, but I guess it isn't right for this game.

Thanks for the suggestions, Mercy. I have a version where the ghost switches to a random angle at the intersections. I'll try doctoring it up by implementing your ideas.

kittiewan: sorry for the delayed answer.

I've looked into your capx, and indeed, I believe the PF can't handle to be run several times each frame, it sounds like too much calculation.

For the part about enemies spawning in the top corner, it has to see with the event to make the enemies move (based on Yann's formula).

Apparently it results in getting a X, Y to 0, and that's why the enemies keep staying in the top of the screen.

I've looked (not that deep) into it, and I guess the formula should be adapted to your project, but I haven't dug much. (you can see it by toggle disable said events, the enemies won't move, but will be spawnt in the "starting rectangle".)

A solution if you really want to use the PF is to "delay" the number of times it gets executed each second (instead of each second, execute it every 10 ticks or so), this could allow the soft to run a bit smoother (no promises there though, it's theory <img src="smileys/smiley17.gif" border="0" align="middle" />).

Mercy is probably right though, the PF might not be the best behavior to use for "chasing ghosts" type.

Thank you for looking into it. This game was really just for learning, so I am not worried too much about it. However, I do want to use the pathfinding for another project. It is easy and fun to use.

kittiewan: Thank you <img src="smileys/smiley4.gif" border="0" align="middle" />

It should be usable in turn-based games and/or with the right combination of cell's side size/layout size / delay of use.

Hey all,

I have played around with this behaviour a bit and it is indeed really useful, but I do have a problem. I think this has been flagged already, but I am not sure, so I give it a try ;)

My Capx

I managed it, to spawn new mobs that instantly get an own Path, but when. This works well for the first mob on each spawn point, but after the first one, each additional mob does show up at the spawn point and jumps automatically to the coordinated 0,0.

Any idea, how to fix this? If possible at all? :)

Update: Managed it to fix the most of the problems but one. After each generation of a mob, the game hangs for some seconds before it resumes. Any idea?

The main problem was with the Demo I used:

instead of:

Lerp(self.PathFinder.getCtXPathList(floor(self.iteration)-1),self.PathFinder.getCtXPathList(floor(self.iteration)),self.iteration-floor(self.iteration))

I used:

Lerp(self.PathFinder.getCtXPathList(floor(self.iteration)),self.PathFinder.getCtXPathList(floor(self.iteration)+1),self.iteration-floor(self.iteration))

My new capx

Kyatric

At last I were able to implement your solution to a working example but am now having massive performance hits. :/ There are probably simply too many paths to calculate as disabling the despawn events did not help the performance. Even my i7 desktop is slowing down.

Instructions (sorry about the unintiutive state of things):

SPACE = End Turn / switch active side

Right click on active side units = pick the unit

Left click while an unit is picked = move the unit

I'm not comfortable with uploading a full capx anymore but can do so privately if you'd like. :)

MovObj_PF_r75.a.capx

MovObj_PF_withPreview_r75.a.capx

Hop! little logic debug. Some of my old decision made the sprite jump directly from the first to the second case. In step mode it wasn't an issue but in smooth mode if you moved by just one cell there wasn't any interpolation.

Ubivis, Wronghands: I guess the current implementation is really not fit for realtime. And/or small Cell Size Side. (bigger cell side sizes over the same layout's size => less computations)

In the current state I'd say it would take another implementation of the PF to perform in real time.

I've been discussing with Yann for some time about such an other plugin/behavior.

For now, I don't really need it, and haven't really time to spend on such side project atm.

As long as you limit and delay the path generations, you may have a use for the PF (especialy in turn based/slow paced games).

Or use a "witness" object that will have the pathfinder and which pathlist the moving instances/objects of the same type (Ubivis, your yellow moving thingies for example) would look/use.

But the path would be actually generated only once on start of layout or any time the obstacles/field is modified. And not for every moving instances.

That would lighten the CPU charge for sure.

Wronghands: I saw some strange things occuring testing your exported project in firefox.

That would lead me to believe that you're not mastering the behaving of your application/logic.

Without the capx, hard to say.

And I really don't have the will/time/energy to be your personnal debugger at the moment, sorry.

You'd have more answers posting a public capx, the exported project pretty much still looks like a prototype.

If you fear for graphical/sound asset, simply make a stripped version with graphic placeholders/no sounds.

Kyatric,

just an idea for future update,

how about when the path finding doesn't find any solution,

it will pick one solution closest to the target <img src="smileys/smiley2.gif" border="0" align="middle" />

Just sharing a real time example, on Chrome it works quite nice already as I set it up to only calculate new paths when the enemy hits a wall (you can place walls by left mouse button and delete a wall part by double clicking it)

ubivis.de/td

So, it can be used for real time in a limited way. I do look forward to see nice updated to it :)