Sorry your browser is not supported!

You are using an outdated browser that does not support modern web technologies, in order to use this site please update to a new browser.

Browsers supported include Chrome, FireFox, Safari, Opera, Internet Explorer 10+ or Microsoft Edge.

DarkBASIC Discussion / Distribute AI processing over game cycles

Author
Message
No Time To Code
15
Years of Service
User Offline
Joined: 22nd Dec 2008
Location:
Posted: 24th Dec 2009 17:06
I'm working on a game where X number of enemies must plot a path to a particular area on the map. Here is some pseudo code to explain the general idea:



There is a noticable pause when the player enters a new zone as pathfinding for X number of enemies takes place. I'd like to find some way to spread the pathfinding processing over the game cycles. I know that I don't need to get keyboard input from the player 60 times per second. How can I get input from player say 2 times per second and the use the rest of the time to process the pathfinding for X number of enemies to eliminate the performance hit from the FOR-NEXT loop for all enemies?
Pincho Paxton
21
Years of Service
User Offline
Joined: 8th Dec 2002
Location:
Posted: 25th Dec 2009 15:39
Use sync rate 0, and then control the timing yourself with timer() delays. Anyway, a 30 loop is so small that it shouldn't slow the game down. Most games can handle a 1000 loop. So maybe your pathfinding is a bit slow.

No Time To Code
15
Years of Service
User Offline
Joined: 22nd Dec 2008
Location:
Posted: 25th Dec 2009 16:45
Quote: "Use sync rate 0, and then control the timing yourself with timer() delays."

Could you point me to an example of a timer() delay?

Quote: "So maybe your pathfinding is a bit slow"

It's an A* pathfinding algorithm. Not sure if it's the algorithm or the way I coded it but I'm going to try a Breadth First Search algorithm and see if it's any quicker. Still would like to know about that timer delay technique...
Pincho Paxton
21
Years of Service
User Offline
Joined: 8th Dec 2002
Location:
Posted: 25th Dec 2009 22:20
If T<= Timer()

`put slowed down code in here although I like fast keyboard input

T = Timer() + 300 'Delay time

Endif

No Time To Code
15
Years of Service
User Offline
Joined: 22nd Dec 2008
Location:
Posted: 26th Dec 2009 04:55 Edited at: 26th Dec 2009 04:55
Thanks Pincho, I'll give it a try!
ffT
Kevin Picone
21
Years of Service
User Offline
Joined: 27th Aug 2002
Location: Australia
Posted: 29th Dec 2009 05:29
No Time To Code,

Without seeing your code, all we can do is speculate. But the pause is mostly likely going to be caused from the path finder chugging away. The more paths, the bigger the chunk of the time.

Now assuming finding a path is the bottle neck, then what you'll need to do is interleave this process across various frames. So the process is allotted a max amount time it can eat up per frame. If the routine exceeds this time, it saves it's current state and exits. Then next frame we re-run this job, reseting it to it's last state. So the routine should continue on from where it left off.

To do this generally means breaking the process in question down into a set of smaller tasks. This is going to be different for every routine obviously. So rather than checking if it's run over time , inside the inner loops, we're checking from some control routine. It'll still be possible for it to overshoot it's allocated time, however it they should never eat all the time. So we're adding a bit of fat to the routine, but gaining the ability to thread it's execution.

I tend to use this type of approach whenever I need my program to appear to keep running while performing various tasks of an unknown length. One that comes to mind is the assembler in the Kyruss tech demo..

Kyruss

No Time To Code
15
Years of Service
User Offline
Joined: 22nd Dec 2008
Location:
Posted: 29th Dec 2009 18:00
Thanks for your response. I think what your suggesting might be beyond my skill set at this time. For this project I'm considering using a different method of creating the paths. I will also look at drastically reducing the number of nodes I'm using for A*. This should speed up the processing and well as result in more realistic enemy movement.

Login to post a reply

Server time is: 2024-03-28 11:39:24
Your offset time is: 2024-03-28 11:39:24