simdevode
12-11-2006 22:21:39
Hi All,
I've been trying to implement a few BFS/A* type algorithms for NPC movement. While it sort of works for me, but I was curious as to what others are doing.
Two issues - First deals with map size and performance. I have a 1000x1000 map, but path planning with 1 pixel grids kills the performance. When I use a bigger grid, and apply a scaling factor, there's a significant loss of accuracy.
Second, integrating NPC movement with physics is even more challenging. For example, if two NPCs collide, I randomly pick one of them, and have it move back few grids and replan the path. This is a very bad hack and I'm wondering what have you guys been doing for this. FYI, I'm using Newton.
Thanks.
I've been trying to implement a few BFS/A* type algorithms for NPC movement. While it sort of works for me, but I was curious as to what others are doing.
Two issues - First deals with map size and performance. I have a 1000x1000 map, but path planning with 1 pixel grids kills the performance. When I use a bigger grid, and apply a scaling factor, there's a significant loss of accuracy.
Second, integrating NPC movement with physics is even more challenging. For example, if two NPCs collide, I randomly pick one of them, and have it move back few grids and replan the path. This is a very bad hack and I'm wondering what have you guys been doing for this. FYI, I'm using Newton.
Thanks.