ChristianHolmes
asked on
PVI Quad in Visual Basic
Greetings,
I'm working on a terrain visibility model. It currently works very well, but I really need to optimize it. I have a height map that is 1000*1000. I am currently doing line of sight calculations in real-time, however with 64 players on the terrain, doing calculations every turn, the overhead is tremendous. Each calculation can be up to 1400+- iterations per test. There are 32*32 tests per turn. This is 1,450,000 iterations per turn. I would like to precalculate the line of sight iterations, but can't simply do it to an array- To do it with an array of bytes would require a Gig of memory. My C++ gurus have recommended a PVI Quad algorithim, which I understand conceptually, but haven't written one. Can someone show me this or any other algorithim to help me speed up this process? I've scoured the net and come up empty handed.
I'm working on a terrain visibility model. It currently works very well, but I really need to optimize it. I have a height map that is 1000*1000. I am currently doing line of sight calculations in real-time, however with 64 players on the terrain, doing calculations every turn, the overhead is tremendous. Each calculation can be up to 1400+- iterations per test. There are 32*32 tests per turn. This is 1,450,000 iterations per turn. I would like to precalculate the line of sight iterations, but can't simply do it to an array- To do it with an array of bytes would require a Gig of memory. My C++ gurus have recommended a PVI Quad algorithim, which I understand conceptually, but haven't written one. Can someone show me this or any other algorithim to help me speed up this process? I've scoured the net and come up empty handed.
Well the answer that comes to mind is to switch language :(
This document might be of help particularly the section on height fields:
http://www.tecgraf.puc-rio.br/publications/artigo_1999_efficient_lineofsight_algorithms.pdf
http://www.tecgraf.puc-rio.br/publications/artigo_1999_efficient_lineofsight_algorithms.pdf
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
That was a helpful article. I have create a psuedo quad-tree that works very well, and requires ONE call to test, so it has increased the speed substantially. It unfortunately has a max. resolution of 50x50, which is actually very sufficient for my purpose.
glad to help :)