Where Should I Share Reusable Pathfinder Code?

[bamby1983]

As the current version of GE seems to lack even basic pathfinder code, I have created my own custom code that can be used as a pathfinder function. It's not meant for complex path finding or working through multiple directional choices in a road. It's intended to be used to walk around irregular structures without using the "Avoid" parameter (as that often results in the actor pointing in the wrong direction while walking, slowing his speed and walking around the invisible rectangle enclosing the object in case the object is irregular in shape).

I'd be happy to share this code with the community and provide a brief explanation on how it can be customized for your game. The code does the following:

1) Calculates the shortest path around an irregular object, taking into account the indents in the object (and not the rectangular periphery limits used by GE)
2) Moves the object to the destination (which is designated by clicking on the destination location with the mouse) along the above shortest path
3) Animates the object so that it always faces the direction in which it is currently travelling (and not just the final destination as GE does)

For point 3 above, I have created a function to make my actor play a different animation based on the direction in which it is moving. This function is called from within the pathfinder function. You can use your own function in its place - no parameters need to be passed or returned. I can provide my directional code as well and you can replace my actor and animation names with your own if you feel like getting into it.

I just want to clarify that this is not a pre-configured function that can simply be called by passing parameters to it (although once this is set up for your game, you can call it using a single function only). It's definitely possible to make it that easy (and I'd be glad if this could be incorporated into Game Editor), but for now, I've taken the easy way out by leaving it game-specific. Therefore, there will still be some basic but minimal code changes required (such as the number of points along the path, regions where the pathfinder is not required as there are no obstacles, etc.) to initially set this up for a specific game or a level in the game.

I'm not sure whether there is a specific section for this sort of thing. Please let me know if there is and I'll put up the code and a brief explanation on what needs to be customized for a game and which function needs to be called for this to work.

[skydereign]

I would recommend putting something like that in the tutorials section. I'm curious on how you did point one, and all of it really. gE's current shortest path uses A* I believe, and does take into account some level of irregularity (it can solve mazes), though MoveTo is generally pretty buggy.

[bamby1983]

I would recommend putting something like that in the tutorials section. I'm curious on how you did point one, and all of it really. gE's current shortest path uses A* I believe, and does take into account some level of irregularity (it can solve mazes), though MoveTo is generally pretty buggy.

You mean there is something other than MoveTo that I can use for default pathfinding? And to think I spent this long on creating my pathfinder code.

I've attached a zip file containing the game along with this message. Here are the steps to access the code:

1) Load "Training Level.ged"
2) Go to "Global Code"
3) Click "Choose", then select "Move Actors"
4) The pathfinder and movement code starts at the function "path_free_move_zone(int x, int y)" and extends all the way down to the end. There are some variable declarations and an "initPathfinder()" at the top that are also related. The latter is called when the view is created. The program flow begins at the moveSoldier() function (it is all the way at the bottom of the code)
5) The big red squares on the screen correspond to the path points. I used actors so I can just drag them easily to wherever I want when I design new levels instead of manually entering the x and y co-ordinates of each point. They are 40 pixels X 40 pixels, which roughly corresponds to the size of my actor plus a little margin. I did this so that my actor doesn't overlap with the obstacle while moving alongside it. You'll notice some values have a "-20) next to them in the code - this is to compensate for this buffer value (half of 40) when it is not applicable. The actors corresponding to these squares are destroyed when the game starts, right before which their a and y positions are saved in a pair of arrays.

The code is kinda big and while i have inserted some comments, a lot of it may not be commented elaborately. If you like, I can write up a brief description of the code flow and how it works, though if you try to figure it out, it should be kinda understandable. Just start at the moveSoldier() function and you should be able to follow the program flow without too much effort from there. The unit moves when to a spot when you right click on it. Right clicking the house or the trees will not work, though. The code moves the actor around the house, including into the notches at the top right and bottom middle. Clicking on the doorstep won't work, but clicking on the road around it will.

[skydereign]

You mean there is something other than MoveTo that I can use for default pathfinding?

No, I was saying that MoveTo uses A*, and that in some cases it does work.

[bamby1983]

No, I was saying that MoveTo uses A*, and that in some cases it does work.

What is A*?

[skydereign]

It's a common path finding algorithm. http://en.wikipedia.org/wiki/A*_search_algorithm

-Edit
Ah, you did use the node based system. For a moment I thought you set it up without the nodes, so I was quite interested in how you managed the efficiency of that.

[bamby1983]

Thanks for the link.

How exactly does MoveTo find its way through mazes? If I ever choose to avoid a certain actor, the unit doesn't enter any spaces that lie within the rectangular box surrounding that actor. I created the walls of the house as a separate actor with a. gif animation and it just walked around the whole thing without venturing into the space between two walls.

[skydereign]

How exactly does MoveTo find its way through mazes?

You have to use clones to construct the maze. And I didn't ever use anything but rectangles for that, so I didn't realize it uses bounding boxes as its method of avoiding other actors.

[bamby1983]

You have to use clones to construct the maze.

Ahhh so you can avoid multiple objects by cloning several instances of an obstacle actor so that the moving actor avoids all of them? If so, that really helps a lot and opens up a ton of possibilities for me. The actor may still face the wrong direction for some of the time if we use the destination and source values to calculate the direction. I guess we can work around that by using x, xprevious, y and yprevious.

[skydereign]

Well, gE auto updates the velocity variables (and therefore angle). So you should be able to use angle to position the actor.

[bamby1983]

I finally got around to using cloned walls to avoid multiple objects and it worked like a charm! And to think I wasted days writing my own pathfinder code.

I guess it would make no sense putting up my code in the tutorials section because the workaround you presented is far easier and better than what I had created. I can even use wall clones with a zero Z-index as space fillers for furniture so that my actor walks around it instead of over it! And it doesn't allow actors to squeeze through gaps that are too narrow for it either! It's all so easy too!

I think I should put up a tutorial on how to avoid multiple objects using clones like this instead of the pathfinder tutorial (if someone hasn't put one up already, that is).

[skydereign]

I guess it would make no sense putting up my code in the tutorials section because the workaround you presented is far easier and better than what I had created.

I wouldn't say that. MoveTo has its share of problems, to the point I ended up using a similar method of path finding. Though your code was definitely on the complex side. If you simplified it and make it easier to use, I think it would make a great tutorial. But, I know that takes time, the main reason why I haven't posted the version I used for apalia.

I think I should put up a tutorial on how to avoid multiple objects using clones like this instead of the pathfinder tutorial (if someone hasn't put one up already, that is).

It hasn't been done, so go ahead.

[bamby1983]

Would you know how to make those GE tutorials that run in-program (like the caveman series of tutorials)? I thought it might be easier and more helpful as compared to a text-based tutorial if I could learn how to do those.

[skydereign]

There is a way, but I've been told not to use them. Essentially they aren't portable to different sized screens, and should be moved away from. Hopefully we'll be able to come up with a better solution, but for now a forum post, wiki page, and perhaps a video tutorial are better solutions.