Archived

This topic is now archived and is closed to further replies.

Thinking slows down movement???

This topic is 4944 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

suppose that i want to write a Pacman program. the red monsters will have to think, and find the shortest path to find ya. Howver, while they are thinking, everybody else has to be moving. But how can this be done??????/ suppose you have this function findShortestPath() and it will take a little time. However i don''t want it to take any time, so that the sprites can move smoothly. But it will take some time which means, everything in the screen won''t move untill the shortest path is found. What can i do????? Is here where we need multithreading?? Someone pls help

Share this post


Link to post
Share on other sites
1) If you''re on a normal pacman-sized grid, this shouldn''t take a noticable amount of time on a modern PC. Most likely there''s some algorighmic improvement you can do to make it 50-100x faster.
2) If you get stuck, precalculate. Storing precalc''d shortest-path-direction information for a 30x30 grid in the stupidest way I can think of will take less than 1 meg. I''m sure you can beat that by a factor of 10.

Share this post


Link to post
Share on other sites
Remember to use time based movement as well. That is where you move things based on how long it was since they moved the last time. This means that no matter what your framerate is objects will move at the same speed.

Share this post


Link to post
Share on other sites
The options (assuming that it does take too long to calculate) that I can think of:

1) Simplify your pathfinding algorithm so that it doesn''t take so long.

2) Find out how to break your path-finding algorithm into chunks. Basically, calculate so much, and if you haven''t found the path, save the information that you have found thus far, and then render a frame. Then you can come back and start where you left off. You keep doing this until you finish a path. The monster will continue to move along its old path that it had previously found, until a new one is found, and then it begins moving along this new path. Sometimes it may take several frames to find a new path, sometimes it might take only one or two. But this shouldn''t matter too much. Path finding doesn''t usually needed to be updated every single frame.

3) Using multithreading. Have one thread do all the pathfinding calculations, and have the game thread just move the monsters along the last found path, as above. The path finding thread would then update the old path with a new path when it is found.

Those are basically recommended in the order in which I suggest you try them. (1) would definitely be easiest, if it can be done. (2) might take some thinking and effort to break the algorithm into pieces and save state information, but (3) could potentially take a lot of effort and cause a lot of very hard-to-find bugs, especially if you haven''t done much or any multithreading before. But I suppose it wouldn''t be bad experience for learning.

Share this post


Link to post
Share on other sites
quote:

But about 2, i don't understand anything because i don't know what you mean when you say "frame" ???



You may want to brush up more on your graphics somewhat. Frames are each distinct rendering to the screen - ie. you draw everything to the screen once, and this is the first frame. Then one of the monsters in your game moves, so you update it, and redraw the screen, this would be another frame. (Note though that in practice you will probably normally update the screen to the next frame even if the game-state hasnt changed).

Hope that helps somewhat.

//EDIT: I stuffed up the quote tag

[edited by - kazgoroth on May 29, 2004 11:39:03 AM]

Share this post


Link to post
Share on other sites
If your pathfinding algorithm for a pacman game takes so long that the game appears to pause, it requires some optimisation.

You should not attempt to break it down or multithread it, beause I believe it can be done so quickly that it will not be noticeable by the user.

I am assuming here that your map is less than 2 orders of magnitude bigger than the original.

Mark

Share this post


Link to post
Share on other sites