Jump to content

  • Log In with Google      Sign In   
  • Create Account


ngoaho91

Member Since 29 Feb 2012
Offline Last Active Yesterday, 09:38 PM

#5136463 Pathfinding avoid a list of polygon

Posted by ngoaho91 on 05 March 2014 - 12:02 AM

@pink horror: i tested with 65 nodes, and do the test 100 times per frame, i'm too lazy to draw a map 6500 nodes biggrin.png. and yeah right, i forgot to mention intersect condition.

 

 


How do you collide a line segment against a polygon?

first i do simple step, collide the aabb of them. if overlap, i do complex step, check collide that line segment to every single line segment of the polygon.

 

 


How do you search for which polygons to test?

i'm using quad tree to divide polygon set. the time to find which polygons to test seem cost logN time(n=number of polygon)




#5136341 Pathfinding avoid a list of polygon

Posted by ngoaho91 on 04 March 2014 - 11:37 AM

Hello, i'm working on a 2D RTS project, no tile-based map. I have a problem on building map data structure & algorithm for that. I already think of a naive algorithm to solve that. Of course it's very slow. I'm looking for an advice from who experienced  biggrin.png

At very first, i have a list of obstacle as polygon like that

 

map.png

 

i decided to build a pathfinding graph, then i travel all pairs of node, connect them if the connection segment doesn't intersect any polygon. this process have O(n^2) time complexity.

 

graph.png

 

after that, on every path query, i try connect every node to A(startnode) and B(goal node), then do dijstra to find path. this process have O(2n) + O(nlogn) time complexity.

 

query graph.png

 

path.png

 

 

That's all, my algorithm works fine(even it's slow) if the environment is static, no insert, remove obstacle. But when the environment turn to dynamic, such as a obstacle removed, i need to rebuild pathfinding graph(O(n^2)), my fps extremely decreased, 120 to 10.

 

Is there a more professional aproach to solve my problem?




#5122978 A* problem with heuristic

Posted by ngoaho91 on 11 January 2014 - 10:36 PM

you just doing wrong when implement the algorithm.
 
according to A*, f = g+h, where f = decision function, g = cost, h = heuristic function.
your h function is right
but your g function, i think something wrong here.
 
take a look at that example
 
Start = 0-0 goal = 4,0

 

1.png

 

Go to 1-0

1-0 has neighbor 1-1, 0-1

Update 1-1, G(1,1) = min(G(1,1), G(1,0) + 1) = 1.4

Update 0-1, G(0,1) = min(G(0,1),G(1,0) + 1.4) = 1

 

2.png

 

Go to 0-1

0-1  has neighbor 1-1, 0-2, 1-2

Update 1-1, G(1,1) = min(G(1,1),G(0,1)+ 1) = 1.4

Update 0-2, G(0,2) = min(G(0,2),G(0,1)+1) = 2

Update 1-2, G(1,2) = min(G(1,2), G(0,1)+1.4) = 2.4

 

3.png

 

Go to 1,1

1-1 has 3 neighbor 0-2, 1-2, 2-2

Update 0-2, G(0,2) = min(G(0,2),G(1,1)+1.4) = 2

Update 1-2, G(1,2) = 2.4

G(2,2) = 2.8

 

4.png

 

Go to 2,2

G(3,1) = 4.2; G(3,3) = 4.2; G(2,3) = 3.8;G(1,3) = 4.2;

 

5.png

 

Go to 1,3

G(3,0) = 5.2; G(4,0) = 5.6; G(4,1) = 5.2; G(4,2) = 5.6

 

6.png

 

Go to 4,0 => finish

Trace path 4-0, 1-3, 2-2,1-1,0-0

 

p/s: sorry, no step "Go to 0-1"




#5117300 database design to store magic attack and effect

Posted by ngoaho91 on 16 December 2013 - 06:13 AM

as rld says, no need to store them in database. i think you should store them in binary file, or even hard-code it in your library. database means slow on setup, and fast on query. but your query quite simple, read only. database system is suitable for huge number of query or complex query. such as you must read 100 records/second, or store 1000000 records to file, or you need to take some data that match some conditions.




PARTNERS