Re: multithreading for pathfinding?

Tech-Archive recommends: Repair Windows Errors & Optimize Windows Performance

If your pathfinding algo takes that long for a single static path,
I'd suggest to work it over. Maybe you can limit the maximum distance,
or heavily reduce details about the scene.

Details only really matter if they're near to the actor. Small
impedimentson the way, wich an actor will have to pass in some
about some seconds shouldn't too much affect it's actual way.
Furthermore you probably want to take dynamic changes to th scene
into account.

So better often use a fast algo to find a rough idea about the path
to choose, and let physics/objectmanagers/whatever focus on the detail.

I don't see your point in thread-friendlyness of DX.
Pathfinding should be done in a separate thread to make use of
Multiple CPUs, but designing a good algo is much more important,
of course. Think about ensureing a minimum path quality somewhere
near to where you'd query results.

Gruss

Jan Bruns

<nospam@xxxxxxxxxx> schrieb im Newsbeitrag news:e4viba02ing@xxxxxxxxxxxxxxxxxxxx
Hello,

I have a role-playing game and I've implemented a simple pathfinding
algorithm (navigate a character from point A to point B avoiding
obstacles). Currently, path-finding is only done for NPC (non-player-
characters) and is performed during combat to get the NPC close enough to
the player to attack.

The problem is that this path-finding algorithm takes a bit of time --
maybe up to a couple of seconds. If implemented in it's entirety inside of
the render loop, it will cause rendering to pause. This leaves me with two
obvious alternatives:

1) Modify the algorithm to do an incremental amount of work per frame,
rather than compute a whole path.

2) Use a seperate thread to do the path-finding, and let the scheduler
sort it out.

The disadvantage of #1 is that I have to figure out how much "work" can be
done per frame -- should I pick a fixed amount of "work" per frame, or
pick a fixed amount of "time" per frame to run the algorithm? (i.e. let it
run long enough to check n collisions, or let it check as many collisions
as it can in n milliseconds)...

The disadvantage of #2 is that DX isn't all that thread-friendly -- for
example, Present() uses a spin-wait for VSYNC to occur, and no threads can
run while it's spin-waiting. Similarly, letting the scheduler sort things
out can lead to unpredictable performance. Another disadvantage is having
to throw locks all over the code.

I'm leaning toward alternative #1 due to the relative simplicity in
implementation.

Anyhow, I'm wondering if anyone in this group has any thoughts on the
subject...

Thanks
Scott

-----------------------------------------------------------
Posted using Android Newsgroup Downloader:
.... http://www.sb-software.com/android
-----------------------------------------------------------
.

Relevant Pages

  • Re: pathfinding and(or) multithreading
    ... I have gone with floodfill algorithm. ... name is "Quick Pathfinding in a Dungeon - Pieter ... the algo is fast as hell. ...
    (rec.games.roguelike.development)
  • Re: Learning cryptanalysis
    ... he picks an algo in function of the date/time and the secret key, ... Even you idea of a one time algorithm is flawed and I will give you the complete reason: There has been available for more than a century a perfect algorithm which is totally unbreakable - it is the One Time Pad. ... The OTP is rarely or never used because the problem of distributing the keys is insolvable - the cost is so prohibitive that only governments use it and even then they use it only for their most important messages, certainly much less than one message in a million. ...
    (sci.crypt)
  • Re: Finding ALG_ID from algorithm name
    ... This works if YOU control the algo names. ... EnumAlgoirthmCallback // name of the callback function to ... // algoInfo.idHashAlgorithm holds the algorithm id. ... enumeration and FALSE to stop the enumeration ...
    (microsoft.public.platformsdk.security)
  • Re: Innovation, my TSP algorithm and factoring, timelines
    ... But now I'm fighting the smaller task of saving my own country, ... OMG you were talking here about the morale of some P=NP algorithm all that are still in their right mind doubt to work. ... JSH still lacks of any Mathematical proof for his algo to work .. ...
    (comp.lang.java.programmer)
  • Re: A few questions about C programming.
    ... >> other algo generated by the same generator. ... He does not just want the algorithm being used to be ... Essentially, he wants an alg. ...
    (sci.crypt)