Follow-up Comment #6, patch #1141 (project wesnoth):
Ha, I had actually tried splitting the screen in two.. still slow.
So, I've tried another way of calculating rectangles that I had been thinking
of. Technically, this way doesn't scale as well as the quadtree approach, but
in practice seems to be better.
I've attached the patch and a savefile. This save is of a situation that both
the current method and my quadtree approach struggle with, but this new
approach handles very well.
Now, it would be really helpful for anyone who can to test this to do
so(again, start wesnoth with --no-delay and --max-fps 1000). My laptop is an
interesting testing ground because it has a very fast cpu and very slow
graphics(since I am currently stuck with integrated graphics in linux).
So, what does this patch do? It may help to refer to the attached image.
Well, first we store all the dirty rectangles until we are about to draw.
Then we take all the vertical edges and sort them by their x-position. These
will then be our events, a left edge will be an in event, a right edge is an
out event. As we go through these events, we keep a list of segments, and a
count for that segment. When we get to a new event, we will make new segments
for it based on its top and bottom. Then every segment affected by this event
will have its count increased by 1 if this is an in event, decreased by 1 if
it is an out event. If the count is zero, then we are at the right edge of
the rectangle we need to draw. In the image black vertical lines are the
events, and then I have marked off the segments that would be stored after
processing that event.
One thing in the patch that I know could be improved is the way that I am
merging rectangles together... I first tried only merging rectangles that
would not add any non-dirty areas to the merged rectangle, but the way I have
it now is faster. Still, I only merge with the previous rectangle which
works... but I think there is a much better way.
(file #5519, file #5520, file #5521)
_______________________________________________________
Additional Item Attachment:
File name: events.jpg Size:16 KB
File name: ghosts.gz Size:12 KB
File name: sweep2.patch Size:6 KB
_______________________________________________________
Reply to this item at:
<http://gna.org/patch/?1141>
_______________________________________________
Message sent via/by Gna!
http://gna.org/
_______________________________________________
Wesnoth-bugs mailing list
Wesnoth-bugs@gna.org
https://mail.gna.org/listinfo/wesnoth-bugs
