# Forum

## The Dijkstra Project

Discuss Artificial Intelligence and Bot programming.

### Re: The Dijkstra Project

jitspoe wrote:You might consider switching to A*. Dijkstra explores all possible waypoints and can be expensive. A* is a bit smarter, so it can be a big performance gain if you have a lot of points.

I have some code here (that I heavily referenced ACEBot source for): http://paintball2.cvs.sourceforge.net/v ... all2/bots/

Your data structures will likely be different, but maybe the logic will be a worthwhile reference.

Thanks jitspoe.
I'm still new to pathfinding, but IIUC, the issue here isn't 'how to (optimally) find the shortest path from node A to node B', but 'how to determine which node is node B'.
OneManClan

Posts: 243
Joined: Sat Feb 28, 2009 2:38 pm

### Re: The Dijkstra Project

It's all about correctly determining the cost to find B, actually. In the example you showed, a blocked waypoint should represent a HIGHER cost than the not so close but visible alternative.
I know FrikaC made a cgi-bin version of the quakec interpreter once and wrote part of his website in QuakeC (LordHavoc)

frag.machine

Posts: 2072
Joined: Sat Nov 25, 2006 1:49 pm

### Re: The Dijkstra Project

frag.machine wrote:It's all about correctly determining the cost to find B, actually. In the example you showed, a blocked waypoint should represent a HIGHER cost than the not so close but visible alternative.

Hi frag.machine
Yes, the thing is, in this situation .. how can WaypointA realise that it's NOT a valid wp from which a bot can reach the owners.origin?
OneManClan

Posts: 243
Joined: Sat Feb 28, 2009 2:38 pm

### Re: The Dijkstra Project

Just to clarify (in case I'm not explaining myself clearly): currently the bot successfully navigates the nodes and ends up at the final waypoint. The final waypoint is always one that is the closest and has 'line of sight'. This would be fine if the bot needed to attack, but in this case I want the (friendly) bot to navigate itself to the owner's position.

The problem is the way the 'final waypoint' is determined. Currently, it's decided by 'the last one the owner touched', but this does not mean that its the closest, or the most accessible. Let's take another look at the scenario I described earlier:

The blue line is the path the owner took. The bot is standing at the last wp the owner touched. Once the onwer is in the position shown, the command goes out "come here, bot", but from the bots current position he cant reach me.
OneManClan

Posts: 243
Joined: Sat Feb 28, 2009 2:38 pm

### Re: The Dijkstra Project

Pretty sure in that screenshot, there should be a jump or rocketjump waypoint over the obstacles between a and the player, there should also be a waypoint at or very NEAR the player. From that waypoint, there should be a path to b, between the obstacles, and to a.

The scenario you show appears to just not have enough waypoints. 2 waypoints for that screenshot is an absurdly small number.

http://mrelusive.com/oldprojects/obots/ ... gamewp.gif

gnounc

Posts: 424
Joined: Mon Apr 06, 2009 6:26 am

### Re: The Dijkstra Project

was the Omicron bot source ever released?
Because they are really smart.

atm i am using an customized bot based on "Globot" with basic waypoint navigation hardwired in my engine, they work fine for me atm,
but they are not really "portable" to other engines.

ofc its easier to copy/paste frikbots, but i like to make my own bots.

drm_wayne

Posts: 232
Joined: Sat Feb 11, 2012 5:47 pm

### Re: The Dijkstra Project

gnounc wrote:Pretty sure in that screenshot, there should be a jump or rocketjump waypoint over the obstacles between a and the player,

In this example, there isn't. The current logic is: if(the bot gets stuck) UseWaypoints() - and current ai returns A as the 'final waypoint'.
gnounc wrote: there should also be a waypoint at or very NEAR the player.

The thing is, even if there was, in an open area such as this, it's easy for the owner to follow the blue path and not come into direct contact with any waypoint. During my testing, I've has to switch waypoint visibility on, so could see the waypoints and intentionally walk into them. This can't be normal.
gnounc wrote: From that waypoint, there should be a path to b, between the obstacles, and to a. The scenario you show appears to just not have enough waypoints. 2 waypoints for that screenshot is an absurdly small number.

True, I've tried to use as few as possible, only put waypoints such that players always have a direct line of sight to one. Maybe that's not enough in certain environments.

Yes, I can see how this works with the waypoints on narrow paths (where a player MUST touch them, but what about (eg) the one on the bottom right, on the floor?

I guess there's 2 questions, the answer to either would solve the puzzle:
Q1: How do the ai Gurus ensure that waypoints detect players in open spaces? (or is 'just make more waypoints' the solution?
Q2: How can the ai know if a bot can fit in a gap? (I suppose a wp on the other side of the gap would solve this particular situation)

Hmm .. I'll try more waypoints, and report back. Thanks for the feedback!

ps is there any reason ppl don't make waypoints of different sizes? To make sure they are triggered in large areas?
OneManClan

Posts: 243
Joined: Sat Feb 28, 2009 2:38 pm

### Re: The Dijkstra Project

touching is stupid. make a sea of waypoints and then just find the nearest.
of course, this will easily push you over the 512 entity limit of vanilla quakeworld...
Spike

Posts: 2883
Joined: Fri Nov 05, 2004 3:12 am
Location: UK

### Re: The Dijkstra Project

This is a common problem with waypoints in general, especially with complex geometry.

I've got a video of the stuff I'm working in with waypoints here: https://vimeo.com/116576240

Ultimately, I think I'm going to do away with them completely and try to use something more along the lines of a navmesh (or some similar system tied into the geometry of the map).
jitspoe

Posts: 217
Joined: Mon Jan 17, 2005 5:27 am

Previous

### Who is online

Users browsing this forum: No registered users and 1 guest