Advance Pathfinding - need advice on approach

[maVado]

I'm working on a Malefiz Game and was wondering if anyone else uses adv. pathfinding obj. and maybe have another idea on how to solve this problem.



Let's say the players current figure is the pink bold dot in the middle, and he rolled a 4. Those pink crosses are the target locations and the smalls dots are possible pathes. How would I do this without wasting too much CPU time?

I would do a fastloop on all available fields and get the path to that location, marking the fields that are 4 turns away. I would end up with around a hundred loopsteps and also around a hundred target fields (most of them overlapping).

Any idea to solve this faster, and or with another extension or without any? (an array is availabe already with the mapping)

[Anders]

I can see that each cell max has 3 neighbors. Try storing the fixed value of the neighboring cells in three different alterable values of the cell. When the player rolls 4, then continue visiting the neighbor cells "recirsively"'ish and place a marker where you can go on the fourth spot. That recursion can be a bit tricky to do in MMF2 maybe. Maybe storing the branches in some list to visit later. You just have to avoid visiting the spots from the direction which you already came.

[maVado]

Do fixed values change on application start? Then I could write those into an array, but only if the do not change. Otherwise I would need a new loop and check the array for neighboring cells.

I was thinking about a pathless approach by creating a detector one all 4 sides of the figure. Then on overlap condition with a field I would set direction and move the object on a grid by 1 field each time substracting from the number the player has rolled. On a junction I would create additional detectors with the number of steps left and destroy the current detector. Then when the value reaches 0, I create a destination object at the detector so that I have a destination the player can click on. Does that make sense?

Then I could use the pathfinding object to move the figure from place A to B in a 4-way movement.

[maVado]

I tried for like 3 hours yesterday to find a non pathfinding solution but without any real success. Visiting Cells and all this took a load of events, when I had like 60 event lines I canceled it and deleted those lines.

So today I got the pathfinding to work. No big deal and it's instant on finding a path, at least on my machine. Now I have another issue which I solved but maybe someone has a better solution.

What I do on pathfinding is that if the player selects a figure on the board it starts a loop. On this loop I let the extension find the path between the current selected player figure and each of the fields the figure can go to. Then I create markers (active obj) on those spots and set a value which holds the number of steps it took to go to that field. Then I compare the step value of those markers to the current roll the player made before and destroy all objects that are different. Leaving me only with the fields left that you could reach with the current roll.

Thats fine. But now onto the gameplay. You have barricade blocks on the gamefield which prevents the player from moving over those. Only with a direct roll you can claim the field with your figure and then move the barricade to en empty field anywhere on the gamefield. However for the pathfinding this is a problem.

I set those Barricade Cells to "NoPath" (which defines a no path field in the extension). There is really no alternative to this, at least what I was thinking of..

The problem now is that when the player figure is the exact number of steps away from a barricade the extension cannot get a path because that field is an obstacle. Therefore it will not create a marker. You cannot really address the field as if you try and change the loop to support something like "no path is found -> do this" it will address all fields beyond the barricade creating more mess then helping.

Now what I did is that I changed the gfx of the marker object to overlap top, bottom, left and right by a few pixels so I can detect for overlapping with barricades on neighboring cells.

I changed the routine to show me only those markers that are lower or equal to my roll, destroying every other marker on the board. And then I compare to the roll - 1 value. So if a rolled 5 would enable my figure to move right on top of a barricade I start a loop on all markers and check those with value 4 (roll -1) for overlapping and if that is true it will create a new marker on top of the barricade.

There is only one problem when figures get surrounded with multiple barricades my method will eventually fail as I only have one detector...

Here is a picture that may help understand my babbling

The green ones are markers, the pink one are new markers with the solution I currently have to detect a barricade.

So back to the extension, im still on the learning process although I use it in another project for multiple enemies and it works nicely. This extension has so many features, maybe I have overlooked something. So any ideas would be appreciated. Thanks

[Random]

You said you loop through all nodes and check each for a path. Can't you check at that point, if there's a barricade on that node? If so, make the node passable, check for a path to it, then make it unpassable again. This way you only get paths onto barricades if they are the target of the move - then, if a path is found, check that the distance is exactly the what the player rolled. If that is the case, place your marker, if not, destroy it (or don't place it).
Oh and.. your game is turn-based, so I wouldn't worry about looping too much. You will probably never notice.

PS: Cool game I played it when I was a little kid!

[maVado]

Well, I thought I could do it without doing each step in a loop checking for a barricade or not but this seems to be the only solution.

I played this game on a website a few days ago and thought thats a good idea for a quick game to make. Well "quick" ...

I will try your idea on the afternoon. Thanks!

[maVado]

Sometimes the solution is so simple ...

I just do the regular find path stuff, but treat barricade as obstacle therefore no path can be found beyond any barricade.

Then I redraw the pathmap but do not map the barricades as obstacles. Instead I pathfind from the current figure to all barricades on the board and check if the current roll is equal to the steps it takes to each the barricade. If this is true I create the marker on top of the barricade.

Problem solved

I feel dumb now ...

[nivram]

maVado, never feel dumb, as we all have questions. Glad you solved your issue.

Marv

[Shawn]

Occam's razor! lol

But as marvin said, don't feel dumb. I've done things in a really complicated way before only to find out I could have done it extremely easy another way

[Stephen]

But as marvin said, don't feel dumb. I've done things in a really complicated way before only to find out I could have done it extremely easy another way

I have done this on several occasions. :blush:

stephen1980