bit-tech.net

Go Back   bit-tech.net Forums > bit-tech.net > Article Discussion

Reply
 
Thread Tools
Old 11th Aug 2010, 11:33   #1
CardJoe
Freelance Journalist
bit-tech Staff
 
CardJoe's Avatar
 
Join Date: Apr 2007
Posts: 11,339
CardJoe is the Cheesecake. Relix smiles down upon them.CardJoe is the Cheesecake. Relix smiles down upon them.CardJoe is the Cheesecake. Relix smiles down upon them.CardJoe is the Cheesecake. Relix smiles down upon them.CardJoe is the Cheesecake. Relix smiles down upon them.CardJoe is the Cheesecake. Relix smiles down upon them.CardJoe is the Cheesecake. Relix smiles down upon them.CardJoe is the Cheesecake. Relix smiles down upon them.CardJoe is the Cheesecake. Relix smiles down upon them.CardJoe is the Cheesecake. Relix smiles down upon them.CardJoe is the Cheesecake. Relix smiles down upon them.
Developer Blog: Making the AI Work

http://www.bit-tech.net/blog/2010/08...g-the-ai-work/
__________________
----------------

I was Bit-tech's Games Editor. Now I'm freelance. Find me at:

www.joemartinwords.com

@joethreepwood on Twitter
CardJoe is offline   Reply With Quote
Old 11th Aug 2010, 22:43   #2
geekboyUK
What's a Dremel?
 
Join Date: Sep 2003
Location: UK
Posts: 17
geekboyUK has yet to learn the way of the Dremel
Cool - this is exactly how I did my pathfinding in my final year degree project! It was a simulator for people evacuating a building to measure bottle-necks in floorplan design... in other words the closest I could get to writing a game for a degree project.

Looks like a very similar method - take corner of each object, pushed out by half width of a 'person' then build net of possible next corners.... then use the net in A*
geekboyUK is offline   Reply With Quote
Old 12th Aug 2010, 22:21   #3
stoff3r
Multimodder
 
Join Date: Nov 2006
Location: Norway
Posts: 184
stoff3r has yet to learn the way of the Dremel
Navigating by corners is a good idea, but how does it improve to just using smaller size squares. Surely the computer can calculate the least amount of squares to the destination?

With cpu's getting more cores and even virtual cores, is it useful for the AI-npc's to have one core each in such games?

How far are we off having the AI seeing in real time and analysing what he sees, in 3d for instance.

Does your game has more complex geometry like windows or stairs etc? And can the visuals be tweaked to other color-schemes? The default could get old pretty fast, and as bit-tech said in beta-testing, it wasn't really that readable.

Sorry for the bombardment of questions, just got really interested
stoff3r is offline   Reply With Quote
Old 13th Aug 2010, 08:49   #4
CardJoe
Freelance Journalist
bit-tech Staff
 
CardJoe's Avatar
 
Join Date: Apr 2007
Posts: 11,339
CardJoe is the Cheesecake. Relix smiles down upon them.CardJoe is the Cheesecake. Relix smiles down upon them.CardJoe is the Cheesecake. Relix smiles down upon them.CardJoe is the Cheesecake. Relix smiles down upon them.CardJoe is the Cheesecake. Relix smiles down upon them.CardJoe is the Cheesecake. Relix smiles down upon them.CardJoe is the Cheesecake. Relix smiles down upon them.CardJoe is the Cheesecake. Relix smiles down upon them.CardJoe is the Cheesecake. Relix smiles down upon them.CardJoe is the Cheesecake. Relix smiles down upon them.CardJoe is the Cheesecake. Relix smiles down upon them.
Quote:
Originally Posted by stoff3r
Does your game has more complex geometry like windows or stairs etc?
I know that Frozen Synapse at least includes obstacles of different heights, allowing for window gaps and cover. You can see them in the pictures above - light blue is a low height object, which players are exposed if they stand behind unless they crouch.
__________________
----------------

I was Bit-tech's Games Editor. Now I'm freelance. Find me at:

www.joemartinwords.com

@joethreepwood on Twitter
CardJoe is offline   Reply With Quote
Old 13th Aug 2010, 09:47   #5
Coldon
Multimodder
 
Coldon's Avatar
 
Join Date: Oct 2006
Location: Pretoria, South Africa
Posts: 208
Coldon has yet to learn the way of the DremelColdon has yet to learn the way of the Dremel
so you are simply using a waypoint based system, albeit the waypoint's are getting auto generated. Grid-based pathfinding is the least effort and the path quality is excellent.

I'm more than sure you would have had better results with a grid-based approach using an optimized A* (priority queue based), theta A* or fringe search.

Seeing as you can now navigate via corners, if you wish to move to a location that isn't a corner, I'm assuming you first have to find the nearest corner, navigate to it and then move to the final location? That is an awful amount of unnecessary work and your path lengths will end up being grossly suboptimal.

you also say that using a grid to approximate the game environment is really inaccurate, that's simply not true, short of using a near-optimal navigation mesh, grid based pathfinding offers nearly the same amount of accuracy, with the added benefit that grid based navigational map updates cost O(1) where as with a navigational mesh this will trigger a whole new subdivision and recombination routine.

Pretty much most of the modern pathfinding research is based upon grid-based navigational maps. I can link you to several papers that might prove useful in the future if you are interested.
__________________
A day in the life of a wannabe game developer: My Technical Blog

i5 750 @ 4.2GHz, ASUS P7P55D Deluxe, 8GB DDR3 @ 1600, GTX 480 @ 900/2000
OCZ Vertex 2 10GB SSD, 3x Seagate 7200.12 1TB, ESI Maya44e...
Swiftech GTZ, Koolance VID-NX480, Swiftech MCR320, XSPC RS240, Swiftech MCP355, XSPC BayRes One
Coldon is offline   Reply With Quote
Old 14th Aug 2010, 18:01   #6
Omroth
What's a Dremel?
 
Join Date: Aug 2010
Posts: 3
Omroth has yet to learn the way of the Dremel
Hi Coldon.

"your path lengths will end up being grossly suboptimal"

This approach produces 100% optimal path lengths in every single situation.

I'm willing to accept that this approach might not be the fastest, however I'm not entirely sure how even an adjusted-grid-based system (which is required as FS' levels are vector, not grid based) would produce the optimal path without an expensive post-step to work out which parts of the grid path could be turned into diagonal movement.

I agree that the recalculation of the nav-mesh is expensive, but FS only ever has to regenerate once per turn and the recalculation takes < 1 second so it's not really a problem. In general, if I find a solution which makes 100% perfect paths in an acceptable time I don't feel the need to further optimise.
Omroth is offline   Reply With Quote
Old 15th Aug 2010, 13:41   #7
Coldon
Multimodder
 
Coldon's Avatar
 
Join Date: Oct 2006
Location: Pretoria, South Africa
Posts: 208
Coldon has yet to learn the way of the DremelColdon has yet to learn the way of the Dremel
To what are you comparing your path length optimality? If you do calculate the paths according to the nearest corner and then do the initial/final movement step to/from it, I cannot see how your paths would be optimal, perhaps you will get at best within 90% optimality but not fully optimal.

even if you level data is vector based a single grid map of the level can be generated and scaled as needed, now I'm not saying you should use grid maps, if your level data isn't dynamic then navmeshes are the way to go. Its jsut I have yet to see a single game using navmeshes in a dynamic environment, relic uses grid maps in DOW and COH.

<1 is a bit worrying, in your case, it seems the game is turn based so that's okay, but if it was real time, that time is unacceptable, for example bioware buts a 3ms constraint on pathfinding searches, so having a single component taking a massive amount of time is usually unacceptable.

I guess I am nitpicking a bit, and at the end of the day, your technique works and that's whats important.
__________________
A day in the life of a wannabe game developer: My Technical Blog

i5 750 @ 4.2GHz, ASUS P7P55D Deluxe, 8GB DDR3 @ 1600, GTX 480 @ 900/2000
OCZ Vertex 2 10GB SSD, 3x Seagate 7200.12 1TB, ESI Maya44e...
Swiftech GTZ, Koolance VID-NX480, Swiftech MCR320, XSPC RS240, Swiftech MCP355, XSPC BayRes One
Coldon is offline   Reply With Quote
Old 15th Aug 2010, 18:20   #8
Omroth
What's a Dremel?
 
Join Date: Aug 2010
Posts: 3
Omroth has yet to learn the way of the Dremel
Can you give me a situation where you don't think it would produce an optimal result? Again - I am perfectly willing to accept I'm wrong on this one, but I haven't seen a single instance of a non-optimal route so far.

We are talking about the same meaning of "path length" yes - as in, the actual distance the unit has to travel on the path.

Ian
Omroth is offline   Reply With Quote
Old 15th Aug 2010, 22:10   #9
Coldon
Multimodder
 
Coldon's Avatar
 
Join Date: Oct 2006
Location: Pretoria, South Africa
Posts: 208
Coldon has yet to learn the way of the DremelColdon has yet to learn the way of the Dremel


in the above example the green dot being the goal, the light blue path uses the closest corner, while the dark blue is the shortest path. Obviously the light blue section is a lot longer than the dark blue. What you can do in your algorithm is, as you explore a node (pop off open list), do a line of sight check to the goal and if its successful, then you have the final path.

So you will terminate the A* search not when the closest corner found but rather when a line of sight check passes. This again is all conjecture based on my understanding of how you are doing your pathfinding, i could be making a wrong assumption somewhere along the line.
__________________
A day in the life of a wannabe game developer: My Technical Blog

i5 750 @ 4.2GHz, ASUS P7P55D Deluxe, 8GB DDR3 @ 1600, GTX 480 @ 900/2000
OCZ Vertex 2 10GB SSD, 3x Seagate 7200.12 1TB, ESI Maya44e...
Swiftech GTZ, Koolance VID-NX480, Swiftech MCR320, XSPC RS240, Swiftech MCP355, XSPC BayRes One
Coldon is offline   Reply With Quote
Old 15th Aug 2010, 22:48   #10
Omroth
What's a Dremel?
 
Join Date: Aug 2010
Posts: 3
Omroth has yet to learn the way of the Dremel
Ah, I definitely didn't make this clear, and my apologies.

For my first step, I add the initial starting position (not a corner) as an actual node, as in I add it with all of the visible nav-nodes.

For the final step, I stop A* when I get to a node which can *see* the end node (not the closest to the end node)... is it possible that that may choose un-optimal result? I'll investigate.
Omroth is offline   Reply With Quote
Old 15th Aug 2010, 23:16   #11
Coldon
Multimodder
 
Coldon's Avatar
 
Join Date: Oct 2006
Location: Pretoria, South Africa
Posts: 208
Coldon has yet to learn the way of the DremelColdon has yet to learn the way of the Dremel
no, that sounds perfectly solid, paths generated in that way should be optimal in regards to the navigational geometry present. Thanks for clearing that up! I was pretty sure that I was missing something

I think that for your current use, your selected algorithm is perfect. Though if you make the environment dynamic at a later stage, it may be necessary to use a different underlying navigational geometry.

Great work so far and best of luck in future. If you ever want to discuss pathfinding algorithms, give me a shout, I've spent the last 2 years researching realtime pathfinding in dynamic environments for my thesis.
__________________
A day in the life of a wannabe game developer: My Technical Blog

i5 750 @ 4.2GHz, ASUS P7P55D Deluxe, 8GB DDR3 @ 1600, GTX 480 @ 900/2000
OCZ Vertex 2 10GB SSD, 3x Seagate 7200.12 1TB, ESI Maya44e...
Swiftech GTZ, Koolance VID-NX480, Swiftech MCR320, XSPC RS240, Swiftech MCP355, XSPC BayRes One
Coldon is offline   Reply With Quote
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT +1. The time now is 09:28.
Powered by: vBulletin Version 3
Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.