graph - Best path algorithm while avoiding moving enemies? -

-

i have general graph/path-finding question had interview.

suppose trying specific node on 2d graph, , there enemy units transversing graph's nodes, searching you: best way maximize chances of reaching goal without encountering enemy unit?

i curious of best algorithm or general approach handle this.

p.s: know enemy units located

assuming want human in dangerous maze do: go ahead , run away whenever see enemy, here simple idea:

  1. run breadth first search once starting goal on whole graph store distance goal in every node. in step, ignore enemies. of course assuming have distance measure in graph. otherwise counting number of nodes during bfs applications. keep distance of last node goal, let call quantity maxdist.

  2. run "small" breadth first search every enemy towards directions. small, because stop after distance of k, k number of graph nodes want keep away enemies or other suitable metric (this represents "seeing"). similar thing in bfs: store distance towards enemy enemy sits in, denote d_i arbitrary node i. in bfs overwrite distance goal in node i maxdist + k - d_i. notice quantity @ least high maxdist. in step need careful on how update node i when enemy has written (keep larger value).

now, in every timestep pick next node 1 node in neighborhood has closest distance goal. since nodes "close" enemy @ least expensive maxdist, automatically avoiding enemies. , if cornered enemies 2 sides, automatically stay in middle between two, hoping long possible 1 of them turns around.

this might not maximize chances, not if can predictions enemy movement. furthermore behaves "stupid" run towards enemy if can't pass until "sees" it, turn around.

but general approach, might best 1 can do, if cannot see enemies far away , if have no information movement, have map see , goal is.


Comments

Post a Comment

Popular posts from this blog

Hatching array of circles in AutoCAD using c# -

-
i beginner in autocad plugins .i have created array of circle using following code. now, have hatch circles in array .how that??how hatch circles @ once? moreover, how can return hatch method , use hatch objects.sorry language.thanks in advance. [assembly: commandclass(typeof(beamsection.class1))] namespace beamsection { public class class1 { //class1 obj = new class1(); [commandmethod("beamatsupport")] public void addlightweightpolyline() { // current document , database document acdoc = application.documentmanager.mdiactivedocument; database accurdb = acdoc.database; promptpointresult ppr = acdoc.editor.getpoint("\nselect starting point "); var ucs = acdoc.editor.currentusercoordinatesystem; point3d startingpt = ppr.value.transformby(ucs); list<double> radius = new list<double>(); radius.add(0.5);
Read more

ios - UITEXTFIELD InputView Uipicker not working in swift -

-
hello trying pop uipickerview view programmatically when user clicks on textfield. have tried doesn't doing anything. isn't working. nothing happening when click textfield class userprofiletableviewcontroller: uitableviewcontroller,uitextfielddelegate,uipickerviewdelegate,uipickerviewdatasource { var itempicker: uipickerview! = uipickerview() @iboutlet weak var gendertxtfield: uitextfield! var gender = ["male","female"] override func viewdidload() { super.viewdidload() gendertxtfield.delegate = self itempicker!.delegate = self itempicker!.datasource = self itempicker!.backgroundcolor = uicolor.blackcolor() self.gendertxtfield.inputview = itempicker } func numberofcomponentsinpickerview(pickerview: uipickerview) -> int{ return 1 } // returns # of rows in each component.. func pickerview(pickerview: uipickerview, numberofrowsincomponent component:
Read more

Python Pig Latin Translator -

-
so have been working on @ codecademy.com while trying learn python. don't know if blind , can't see why won't work or what. here's code won't let me use. function print variable if had typed in , print "empty" if didn't type anything. print "welcome english pig latin translator!" original = raw_input("what's name?") if len(original) > 0 print original else print "empty" if len(original) > 0 else the above lines contains syntax errors. try: if len(original) > 0: else: note added colons, ( : ).
Read more