waypoints

[Nahuel]

Hi everybody, is there some way of make the monsters folloew the player through waypoints left by the player when he is not visible? is there some example of it or something like that?
Thank you in advance!

[daemonicky]

I have not tested it.

Make monster follow player :
There is movetogoal(float) function for monster to move by a fraction to the goal. I im not sure if it this fraction is fraction of distance or just time delta; if it is the first, then you compute fraction by by delta time or frame time / ( vlen(goal - monster position)/velocity of monster ) = frame time / time to reach goal = fraction to reach goal.

Not sure what "goal" parameter for monsters is, so try target or goal.

How to make waypoints :
never did them. And you probably know how to make them. I guess they are just entities which you spawn with some classname, probably "there_walks_an_invisible_player". And you spawn them places where enemies should go; simple version could be spawn at regular intervals, or detect player passing edge = traceline between players current position and last waypoint does not have trace_fraction 1 (comes with a nice feature of monsters falling to the lava if player is on bridge ... monsters in Quake do some zig zagging to avoid this, it is somewhere in monsters ai in original Quake C ... ).

It makes me wonder, whether there is not a library for making waypoints automatically ...

Or not waypoints, areas (polyhedrons, polygons ...), where monsters could freely move, looks better to me (monsters is free to move anywhere inside it; if it should pass border then it you check if other area is fine [you can memorize which areas are adjacent and fine ]; if you plan which path to choose, then nodes for pathfinder are not waypoints but these adjacent areas).

Article on areas http://www.cs.uu.nl/docs/vakken/mpp/oth ... _fails.pdf . Oh, and it is called Navigation Mesh .

[Nahuel]

you are right, I believe that the waypoints generated by the player are not a good resource.
I want to achieve the following thing for example: the player escapes of a demon on having gone on from a room to a corridor with several doors. Then it opens one of these doors and gets inside a smaller room. When the demon sees that his "huntarget" is already not more visible firstly it goes to this corridor (this if it would be achieved with waypoints predifined in the map) and one begins to destroy for one the doors of this room, the doors would be "targe"t until it finds the player. If it does not find it and remains without "secondary target " the demon begins to stroll around for the whole map. I do not know if it is too complicated.
I am going to try to do something,

[daemonicky]

for example: the player escapes of a demon on having gone on from a room to a corridor with several doors. Then it opens one of these doors and gets inside a smaller room. When the demon sees that his "huntarget" is already not more visible firstly it goes to this corridor (this if it would be achieved with waypoints predifined in the map) and one begins to destroy for one the doors of this room, the doors would be "targe"t until it finds the player. If it does not find it and remains without "secondary target " the demon begins to stroll around for the whole map. I do not know if it is too complicated.
I am going to try to do something,

No. It is not complicated once you are familiar with some patterns.

I was thinking how to do it ... well you do it with SSS.

SSS? State Space Search, they are all alike. http://en.wikipedia.org/wiki/State_space_search . They are Depth First Search (used in Prolog - logical programming language), Breadth First Search, BIDirectional Search, A* ... and they seem to follow this pattern :

* from all states I want to check I choose one
* I will examine it if it is not what I am searching for,
* if it is i am finished, hooray
* if it is not I replace it with all states which are implied by this state (which this state leads to)

You may have heard about them, A*, Detph First Search, Breadth First Search .... they are State Space Searching algorithms. And they are more-or-less alike. They really differ in details. Lo. DFS has states in stack, but BFS in queue. A* uses some heuristics to choose the node, but BFS and DFS always choose the top/first one.

And one more thing. You have to remember or mark those which you examined. You dont want to run in infinite circles, do you?

Well, I dont like how it is presented everywhere just like a tree. It is, but I think it is much more easier to undesrstand these guys by seeing the tree and how these nodes (states) are evaluated. There are some things which might help you understand it more :
http://en.wikipedia.org/wiki/Breadth-first_search animation on wiki is how these nodes are examined/replaced
http://www.csie.ntu.edu.tw/~wcchen/algo ... Graph4.htm
http://www.mrleong.net/tag/depth-first-search/ ... missionaries canninbals, problem I learned this stuff on
http://upload.wikimedia.org/wikiversity ... earch2.png

for example: the player escapes of a demon on having gone on from a room to a corridor with several doors. Then it opens one of these doors and gets inside a smaller room. When the demon sees that his "huntarget" is already not more visible firstly it goes to this corridor (this if it would be achieved with waypoints predifined in the map) and one begins to destroy for one the doors of this room, the doors would be "targe"t until it finds the player. If it does not find it and remains without "secondary target " the demon begins to stroll around for the whole map.

Your problem would be something like this.
States are rooms.

Put first room into list. Is there a player? Yes -> kill him! and you are finish. No -> replace room you just examined with all adjacent rooms. Repeat.

You have to insert walking into these rooms, so monster actualy DOES SOMETHING instead of being smartass . And also walking back so You can explore all the possible paths. Like this :

Put first room into list. Walk to this room from current position (you are there already, but only for the first time) Is there a player? Yes -> kill him! and you are finished. No -> replace room you just examined with all adjacent rooms ... if it does not have adjacent room walk back to room from which you get to this rooom. Repeat.

Then, well, player might escape, you might not found him at all / he slipped behind your back. You have to constantly restart this routine.
If the player is there you have no reason to keep the data or doing this routine so erase the list and go to hunting mode.


I wanted to write some STRIPS http://en.wikipedia.org/wiki/STRIPS#A_s ... PS_problem in Quake for my game, wlell, it seems I will be doing her in Blender. But I may try to make some quick demo in Quake , probably together with Evaldraw http://www.advsys.net/ken/download.htm .
STRIPS are used in FEAR. They so far seem to me like classical SSS with some pre/post-conditions. Ill see how it will be while implemening it ...

[daemonicky]

walk to goal, if locked room in your way -> bash the door, continue walking to your goal

You can do it in think function where you will put current walking anyway.

And these states shoul be some data structure. I know how Quake is poor about them. So You can do a group of entities which have some classname are somehow chained ... well I dont know, I never did AI in Quake, so I have also never abused entities to implement SSS.

[daemonicky]

Hi everybody, is there some way of make the monsters folloew the player through waypoints left by the player when he is not visible? is there some example of it or something like that?
Thank you in advance!

I guess you wanted a monster to hunt a player. That was what I posted.

If you wanted to make some Hansel and Gretel then it would be similar I think.

And waypoints should be made when traceline between last waypoint and current position is obstructed or too far. I never did it it is just how I would approach it. But I think you dont need waypoints. You need these rooms, and have them connected / so monster can try all the possible paths returning if it fails ... and searching from scratch when it tried all the paths.

In case you would find monster too predictable. Choose randomly wchich path it examines.

[Nahuel]

daemonicky

I do not know anything about it!
I believe that all this cool stuff is too much complicated for me (a noob in qc) and even for qc (at least the ssqc)!
have you played scourge of armagon of quake? well, there the "gremlins" has a complex AI for what it is a monster in qc. They can steal weapon and feed on corpses to multiply. His ai is complex and interesting. It is an excellent base and it is in open code, you should check it, as the system of waypoints of FRIKBOT. Although of these bots already is something very different. I do not want to be too complex because I do not know so much about programming like you... haha, I am an only a fan of the qc!
Anyway thank you very much for the information, you turn out to be very capable, I believe: has you tried to use UDK? I believe that with his good ideas and theoretical bases you would do big works there!
Greetings and thanks for the answers.

[daemonicky]

Thank you very much for information. UDK looks great and I will check out gremlin and Frikbot.

You can try evaldraw, you write code in it and it is executing as you write so You have great feedback . http://www.gamedev.net/topic/466106-ken ... -evaldraw/ It is about math but you will get it by deleting and messing with the code.

What are you planning to do now about your waypoints? I mean, it would be pity if you stopped.

[daemonicky]

I got solution.

- You pass traceline from each door or the ogre (I mean the place where the doors are ...)
- if it hits the ogre he walks there

Now. You dont want to go to same place all the time or be using just one door or be circling right? This solution will not be working 100 % .



- mark each door you used gone trough by float doors_search_id;
- make a global variable float this_search_id;

Basically door_search_id tells you wheter the door was searched at current path searching,
if it was already searched (doors_search_id == this_search_id) then it means you have been there and you have to ignore the door (otherwise you will be making circles); if these numbers are different you can walk there.

You set door_search_id = this_search_id after you walked trought this door.

If you searched all the doors this_search_id += 1 , initialize door with doors_search_id different from this_search_id

Hmm, this is will not let you go back and search other possibilites.
So this number must be changing differently . Well it must be following such pattern
http://docs.yworks.com/yfiles/doc/devel ... dfs_1c.jpg .

We will now folow that picture .

1. All door seach id start at a new search are set to zero.

2. (a) If it is zero when hitting player you can go there. You increment this number by one.
Your this serch id is set to this number. Well it is a new path, right?
You can see it on a picture ... 1,2,3,4,5,6

3. When you have no path at all, it is number 6 on picture, you will only accept number which is lesser than your number by one. You can see it on a picture, you are on 6 you go only to 5, 5 has no other option so you go to 4, ...

4. Now you are on 3. Horray there is some zero path! You will make new serched door number 7 (which is number of door you checked last + 1).
It is similar to (a) Well you can image you checked last number 0 so the first number is 0 + 1. Actually it is correct procedure to set number which was 1. I did it for simplification .

Hmmm, id does not work either because it does not handle the going back correctly. You can see it yourself, number 7 does not have 6 ....

that door remembers number which you searched before you arrived there. So in picture door 2 remembers 1, 3 rembebers 2, 4 rembers 3, 5 remembers 4, 6 remembers 5, 7 remembers 3 ... 11 remebers 1 (NOTE: the start has number 1)
2. When you go forward you just serch for 0, those were not visited yet, that will work.
3. When you go back to seach other paths .... You remeber the number of the last door you have been at (6). If there is no door which you can go to from this door (well there is no door with 0 which door 6 is connected to) you go to the number which it (6) has as previous (5). .... this is repeated automatically when you get to door 5 ...
1. When you start new search all doors have previous number 0, that will work.
4. When you go forward you set the new number to the maximal number, and previous to the previous .... so 7 has 3 .... 9 rembebers 2 ... 10 rembmers 9 ... 11 rembebers 1 ...

I am sorry for this mess, but I hope You can puzzle trough it somehow. Use the picture and have
enity door
{
float my_number;
float previus_number;
}

global float maximal_number; // ogre searches and it contains what maximal number so far he got by his search

entity ogre
{
float i_serched_this_number_last;
}

[daemonicky]

Code is something like this :

Code: Select all

// new parameters for door in pseudocode
entity door
{
float my_number;
float previus_number;
}

global float maximal_number; // ogre searches and it contains what maximal number so far he got by his search

// new parameters for ogre in pseudocode
entity ogre
{
float i_serched_this_number_last;
}


[b]() init_search =[/b]
{
maximal_number = 0;
ogre.i_serched_this_number_last = 0;
//
// doors to zero
//
while(1)
{
d = find( world, classname, "door");
if (! d) break;
d.my_number = 0;
d.previous_number = 0;
d = d.next // dont know proper syntax
}
}

[b]() search_door =[/b]
{
//
// find new door
//
while (1)
{
door = find( world, classname, "door");
if (! door) break;
traceline(ogre,door)
if (trace_fraction == 1)
{
if (door.my_number == 0)
{
walk ogre to this door entity
door.my_number = maximal_number + 1;
door.previous = ogre.i_serched_this_number_last;
ogre.i_serched_this_number_last =  door.my_number;
maximal_number += 1;
ogre.goal = door;
[b]return ; [/b]
}
}
door = door.next // dont know proper syntax
}
       
//
// go back
//
// there is no door he can go to
// assume all door are perfectly visible from each door
while (1)
{
door = find( world, classname, "door");
if (! door) break;
if (door.my_number == ogre.i_serched_this_number_last)
{
ogre.i_serched_this_number_last = door.previous_number;
bprint("searching another alternative");

ogre.goal = door for which my_number == ogre.i_serched_this_number_last;
// wow, I just realized you can do it by pointer to entities :-D

//
// there needs to be something done so that ogre know he is searching back
//
//
return;
}
}
door = door.next // dont know proper syntax
}       

}

[daemonicky]

ogre.goal is where ogre goes next i guess. I am not sure how it works internally. I never programmed AI in Quake (until now ).