About obstacles: Yes I need to draw some obstacles on the map. I just tested a newscript on irregular sufaces…
About avoidance: I did something like what you said before. But finally, I made an individual avoidance system because players are not always in single file. Anyway, I"m having the same issues as before. Avoidance is not simple to me. There are many types of avoidance: Avoidance beetween players in the same group (I made a simple system (3 lines of code) to slow down players if their nearest neighbor is too nearby and its index in the sorted by distance to goal player group is <… Avoidance beetween a player and a static group (for that I can make the squares on the grid as obstacles when a group has reached its destination (but I made another system based on width and height of the group and distance beetween the group and the nearest obstacle…). But the most important part is avoidance beetween 2 objects or 2 groups moving… My system works in some situations but not all the time. I tested RVO (reciprocal collision avoidance) Blender system but it does not work correctly. I think the principle of RVO is good but I think Blender has not the lastest implementation of RVO 2:
So first I would have to translate C++ implementation in python, and then to adapt the code to the pathfinding grid system. And I think that’s too hard to me. I didn’t find enough understandable documentation on RVO to understand correctly the concept. And it would be a very long stuff.
I don’t want to use physics in Blender because it slows down the program.
So… I think I’ll try to improve my own avoidance system to take into account situations that don’t work fine for the moment.
EDIT: And I haven’t updated my present avoidance system to take into account irregular surfaces… I’ll update later.
It’s looking really great. The agents move very smoothly, and they are filling up the destination array very nicely now.
I couldn’t solve 2 moving group collision either, but I made my game turn based so I don’t have to worry too much about that now.
With same team movement I gave everyone a movement priority, agents far away from their destination will wait for agents who are nearer to finishing. If they wait too long they go in to dormant mode and lose their route. It sometimes leads to traffic jams, but I’ve stopped worrying about that too much. Even in real life there are traffic jams, I don’t want to make my agents too smart or they’ll not be believable.
I’ve implemented all the time saving elements I can in to my pathfinding function now but it’s still not that fast, but I think it’s as close to fast as I’m going to get it for now. Right now I’m looking for better ways for the AI to use pathfinding and other tools to have smarter behavior. I’ll probably come back to path finding later, so I’ll keep an eye on your project so I’ve got some ideas for the next time.
Thanks Smoking_mirror. I’m wondering if I make a turned based or other system. Anyway, thank you for your advices!
(I had a look on your GLSL project. That’s a very nice effect!)
I think I’ll abandon this stuff or maybe just make an obstacle function with mathutils intersect plane plane or something but I’ll need your help Smoking_mirror
I tested out the mathutils functions and they weren’t much faster than using ordinary raycast collision detection. It might make a difference if you have 200 agents, but I don’t know for sure.
Hello! I think there is a misanderstanding. Sorry for my bad english. When I speak about “obstacle function”, I mean a function executed at game start (and each time we add an obstacle on the map) to place obstacles on the grid (get the position of the obstacle and update the grid of nodes to indicate: this node is not walkable).
Attachement deleted…
The mathutils intersect functions could be usefull (Currently, my obstacles have only one property: radius > so all obstacles are squares on the grid. But I could add another sorts of obstacles…). For example, like in the picture above, I could get the line beetween 2 “blocks” with mathutils intersect plane/plane and say that each node on the line is not walkable. But I don’t know how exactly how to make that.
Hello Smoking_mirror! Could you give me an example of what you made to get the data geometry from meshes and unsing point inside area to set nodes as blocked? I confess that I don’t understand exactly the mechanism. Thank you very much!
It builds a list of triangles defined by their corner points. When placing nodes later you can check if a node is inside one of the triangles.
There are a couple of ways to speed this up and increase performance:
Use classes or dictionaries for the triangles instead of a list.
Define bounding boxes for the triangles (or obstacle object). You can then do a bounding box check before doing an intersect check, to remove many of the triangles from the search list.
In either case it might be good to set up the dictionary structure like this:
So you can check by object first, using the bounding boxes, then if the bounding box check is true, then go in to the triangle check.
The other good thing about using a dictionary is it makes it easier to do dynamic obstacles, so that if an obstacle object is moved or is deleted, you can go in to the dictionary and edit just the data for that obstacle, not the whole list.
By the way, the attachment you used earlier didn’t upload properly, I couldn’t see it when I tried to open the link.
Thanks very much! I’ll study your .blend and all what you say here and try to make something in my .blend. The attachement was just a picture of Age of Empire 3 showing a wood wall. I don’t know why it disappeared… Thanks again!
Here is the final version (before bugs corrections and maybe documentation add) of my
Jump Point Search implementation in Blender.
changelog:
WayPoint system removed (It did not work well)
Code simplification
Little build mode added and obstacle function improved (made by Smoking-mirror)
For the river, I used Martinsh water shader (settings are not perfect)
I reduced the size of the grid to avoid freezes during game and limit
the number of selected players to 24.
Dynamic obstacle avoidance beetween players removed. My system did not work well)
This file is not a RTS game template, but many functions can be usefull to make
a strategy game. Most of functions are written by professionnals or confirmed amateurs
(for the jump point search algorithm, qiao http://qiao.github.io/PathFinding.js/visual/
and for the rest, Smoking_mirror (obstacle function and some other things), Mobious from
Blender Artists. I also received the help of Monster and agoose77. And some advices from moaaa
(Blender clan french forum). For the river, I used Martinsh water shader.
So thanks very much to them. For the most part of the scripts, I just adapted their code
to my needs (certainly in a maladroit way), but I tried to keep only things that seems
to work almost fine and put aside the rest.
The file remains incomplete and your suggestions are welcome.
Have a good day!
Commands:
In select mode (default): ONEKEY (en haut à gauche du clavier)
Thanks! My initial aim was just to implement Jump Point Search algorithm in Blender. At last I implemented many other things. But I think I’ll stop that stuff for the moment. Or maybe I’ll make a more simple file with just jump point search algorithm to permit people to understand the principle of the code and how to use it.
But feel free to improve it if you want and post your modifications here. For the rotation of the camera, I’ll take a look and see if I can do something…
That works here:
But in my file, players are 17 BU units above the ground. I’ll try to change that…
