Hi all.
I like games but I don’t like gratuitous violence. I was wondering if it is possible to create navigation paths from within the game so that you could have a game where you build things similar to the way Roller Coaster Tycoon works. Your characters could only go where you have designated a path. I tried searching for variations of pathfinding but didn’t see an answer to this question.
Thanks for any information you can supply.
Best regards,
Bob G.
Lots of questions in this forum. Not many answers.
There are some short answers to your question and some much longer answers. One short answer is yes, this behavior is possible to accomplish with BGE. How you would go about implementing it is many long answers, and they require you to have some prerequisite understanding of programming for it to be a fruitful conversation to have. Another short answer is no, as in no there is not a simple built-in mechanism for this. It is a specific system that you would have to implement yourself.
But assuming you have a basic understanding of computer programming, all a path is, is a set of coordinates and a data structure to relate them to each other.
If travel down the path only needs to be one way, and it doesn’t fork, it can be encoded as a linked list of coordinates. If travel can be in two directions and it doesn’t fork, it can be a doubly linked list of coordinates. If there are branches in the path and travel down the path requires choosing between two or more branches, you will have to have a tree structure and tree walking algorithm.
This sort of thing is not super complicated, especially if you know a bit about data structures and how to get the most out of them. But if you are wanting something you can do completely with logic bricks you are probably going to be disappointed.
Lots of questions in this forum. Not many answers.
Many many questions on this forum get answered, tens per day. But not all questions have satisfactory answers that can be addressed in a paragraph or 2. The people that answer them (or don’t) have absolutely no obligation to even read your posts. It is important to keep this in mind when you ask a question.
There is a reason no-one has answered. Because no-one knows a way of doing this.
Unless you want to code your own path-finding, and play around with vertex manipulation during runtime, which believe me, is not fun.
I know a way of doing it. I have described roughly how you would go about it. You don’t have to do any vertex manipulation either. You just compose a data structure that contains coordinates marking points along the path and orient/move along it. Heres a really rough version for 3d pathfinding, which could be adapted for non-branching paths in 2d or 3d.
follow.py.zip (1.13 KB)
As I understand it, the existing ‘pathfinding AI’ in 2.64(2.65,2.66) uses a ‘nav map’ which is merely a copy of a selection of tiles from the mesh used to represent the ground. Wherever there is tiles connected together in the nav map, the pathfinder AI can a find a path to a specific location along those connected tiles. What I had in mind was to generate a nav map that is compatible with the existing pathfinding AI but create it in-game by highlighting a ground mesh tile and copying the selected mesh tile to the nav map.
Basically the nav-map would be generated as empty. After starting the game, you would select a single mesh tile from the ground and copy it into the nav map. Something like that. Repeat the process to create paths. Use the path to have your npc’s wander around and/or go to various points at which they would do something.
I have a little knowledge of programing but I am not familiar with how mesh data is structured. Also I would need info on the structure of a nav map as it is implemented in 2.66.
Short answer:
Yes.
Long answer:
Depends on a great many things, or as Mordin would say: “Big picture made of little pictures. Too many variables.”
There are a great many things to consider, before committing fully to any one form of pathfinding - all of which I will summarize as the following:
Complexity of the Scene VS Complexity of the Characters
Usually I find that, that overrules everything else: until you have established those two, through rigorous study and carefully weighed calculations - only then, would I advise you to really dive into making the pathfinding.
Otherwise you’ll probably end up wasting a great deal of time, re-inventing your own wheels over and over and over again - probably losing a great deal of motivation in the progress.
A couple of recommended reads:
http://www.jamisbuck.org/presentations/rubyconf2011/#title-page
http://en.wikipedia.org/wiki/Pathfinding
http://www.ai-blog.net/archives/000152.html
Good luck!
I think in the case of building custom nav meshs for use with BGE steering actuator or the KX_NavMeshObject interface, you have some options, but they are very limited. The main limitation would be that you cannot dynamically change the topology of a mesh. You can’t add or remove anything, you can only modify certain properties like location & normals.
So… yeah you can transform/duplicate navigation meshes in game, but without some serious magically hackery (like generating blend files with your game and dynamically loading them), it doesn’t seem like you can just build up new nav meshes with arbitrary topology.
Ok, I see the point everyone is making. It apparently can’t be done with the existing game logic. It sounds like what would be needed is new (added) game logic. I have never gotten into the developer side of Blender but I might take a look at the source code and see what can be done.
I assume that Blender mesh data is merely a structure of some sort. That is implied by the ‘Data Block’ way in which any object is defined in Blender. I’ve never worked with Python but I have a fair background in using ‘C’ and a little experience with 'C++". What’s needed is the ability to select a face within an object, and to copy sufficient data about that face to another object within the game. That is; copy a tile from a ground mesh to a nav map. Then, of course pathfinding AI might (or might not) need to be updated to recognize the change to the nav map.
Being able to do this kind of manipulation would be nice for other aspects of gameplay. specifically being able to build things within the game by adding objects. Again, I’m thinking of the Roller Coaster Tycoon style of game play.