Page 1 of 1

Line Tower Wars & Linked Lists

Posted: Fri Apr 29, 2016 4:15 pm
by Ian
Edit: I figured out a solution soon after typing this, but I would still like your suggestions.

Hi 3ICE. I've been looking at ltw 7 lately and I am trying to use it to learn some new stuff. I was wondering how I could correctly setup the leak removal of creeps that exit lanes. Player sending is currently done using a linked list, but it seems that one linked list can't be used to move leaks from one lane to the next. How exactly should I set this up without doing checks to see if the next lane's player is dead or not?

If you haven't played Line Tower Wars 7, then a quick game with more than 2 computer players can teach you how sending works. The computer players will not do anything.

http://www.epicwar.com/maps/95 (Link to map)

An example:
(Lanes)
1 <-> 2 <-> 3 <-> 4 <-> 5 <-> 6 <-> 7 (and then 7 points to 1, and 1 points back to 7)

If lane 6's player dies, then lane 5 now points to 7 and lane 7 points back to lane 5. Lane 6 can still have creeps in it, and these creeps need to move to lane 7 when exiting lane 6.

1 <-> 2 <-> 3 <-> 4 <-> 5 <-> 7

6 -> 7

Now if lane 7 dies, then lane 5 now points to lane 1, and lane 1 points back to lane 5. Any creeps that are still in lane 7 now need to move to lane 1 when exiting lane 7.

1 <-> 2 <-> 3 <-> 4 <-> 5

7 -> 1
6 -> 7

But, if any creeps are still in lane 6 while this is happening, they're told to move to lane 7 (a dead lane now). I need to know how to directly tell lane 6 to send creeps to lane 1 instead of just checking each lane to see if its dead and updating the lane data.

I'm doing this for practice and want to know how this can be achieved.

Re: Line Tower Wars & Linked Lists

Posted: Fri Apr 29, 2016 4:56 pm
by 3ICE
LTW is map #95? Awesome. (The first map ever on epicwar is Wintermaul DV 4 by Duke-Wintermaul by the way.)

I don't see why you needed the doubly linked list for this. (Creeps don't go backwards, or do they? It's been a while since I played LTW...)
A singly linked list would be easier to manage, as there is only one reference to update when a player dies. (Plus a second pass to eliminate the sending of straggler creeps from already dead players to the player who most recently died, which you want to avoid.)

I ran into a similar (though not as elegant) issue with my click wars map. Many empty lanes would lag the game because I did not use a list (not even singly linked, nor anything else, really. Nothing clever like that.) I just brute forced a quick solution like this; teleport every leaked creep to the start of the next lane ignoring slot status, but with a special behavior of dead lanes instantly forwarding everything sent to them on to next lane's spawn:
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12
And of course it's circular with 12 pointing back to 1 as expected:
12 -> 1

This forwarding trick paired with your linked list is already an okay solution since it will only be used rarely, for a few dozen creeps at most.

But without the linked list (what I had originally) it wasn't good enough: If only two players were playing for example, then red could send just fine, but each time blue sent to red the creeps were actually teleported more than 10 times! (Imagine the lag...)
Later fixed with a pair of JASS functions that smartly chose the target lane to teleport to, skipping dead players, but that version of the map is as of yet unreleased because somewhere along the lines I introduced a desync bug into it.

I'm also curious; How did you solve it?

I think this redundant double linking could actually be a good solution here. Kind of. Keeping track of the back references you could update the stragglers every time another player dies to point to the correct lane.

The above situation continued, and played out in full:
1 <-> 2 <-> 3 <-> 4 <-> 5
6 -> 7 -> 1

then 5 dies:
1 <-> 2 <-> 3 <-> 4
5 -> 6 -> 7 -> 1

then 2 dies:
1 <-> 3 <-> 4
2 -> 3
5 -> 6 -> 7 -> 1

then 4 dies:
1 <-> 3
2 -> 3
4 -> 5 -> 6 -> 7 -> 1

then 3 dies:
Game over, no need to update anymore.

p.s.: From this point:
1 <-> 3 <-> 4
2 -> 3
5 -> 6 -> 7 -> 1

had 1 died instead of 2:
3 <-> 4
1 -> 3
2 -> 3
5 -> 6 -> 7 -> 1

Re: Line Tower Wars & Linked Lists

Posted: Fri Apr 29, 2016 5:29 pm
by Ian
I keep a list of lanes that each lane is receiving leaks from.

Starting out:

The list:
1 -> 2 -> 3 -> 4 -> 1

Receive data:
1: 4
2: 1
3: 2
4: 3

So, let's say lane 3 dies.

Go through the lanes it receives leaks from and set the next data to 3's next data.
Then, add 3's receive data to 4's receive data.

The new list:
1 -> 2 -> 4 -> 1

Receive data:
1: 4
2: 1
Edit: Three should be empty here instead of having 2.
3: 2
4: 3, 2

Now if lane 4 dies, we go through 4's receive data (3 and 2) and set their next data to 4's next (which is 1)

Now, the list is 1 -> 2 -> 1.
Four's receive data now gets added to 1's receive data:
1: 4, 3, 2
2: 1

Do you think I've missed anything?

Re: Line Tower Wars & Linked Lists

Posted: Fri Apr 29, 2016 5:39 pm
by 3ICE
Ian wrote:Go through the lanes it receives leaks from and set the next data to 3's next data.
Then, add 3's receive data to 4's receive data.
This is the perfect solution.

Edit: Compare with mine:
3ICE wrote:Keeping track of the back references (your: lanes it receives leaks from) you could update the stragglers every time another player dies to point to the correct lane.
The two are identical except yours is worded better; it gives the explicit solution.

Re: Line Tower Wars & Linked Lists

Posted: Fri Apr 29, 2016 6:09 pm
by Ian
I don't see why you needed the doubly linked list for this. (Creeps don't go backwards, or do they? It's been a while since I played LTW...)
When removing a lane from the list, don't I need to store the previous lane to set that lane's next to the removed lane's next?

1 <-> 2 <-> 3 <-> 1

Remove 2, previous is 1, next is 3.

1 -> 2 -> 3 -> 1

Remove 2, how do I know to set 1 to 3? How do I know that 1 is before 2?

Edit: I'm aware that my lanes are never removed, but I do need a doubly linked list to optimize the removal of a node. Correct?

Re: Line Tower Wars & Linked Lists

Posted: Fri Apr 29, 2016 6:33 pm
by 3ICE
Node removal in singly linked list requires the use of two pointers to iterate over the list:
Sorry pseudocode untested Edit: it's also wrong, see reply below wrote:

Code: Select all

pointer target = 2
pointer p = first
pointer q = p.next
loop while p != first
  p = p.next
  q = q.next
  if q == target
    q = q.next
    //win
    return
  end if
end loop
That "win" comment explained: when you reach the target you want to delete (2):
p will point to 1, while q will point to 3. Set p to q, done.
(And if you need to reach 2 for deletion, that's of course still referenced in target and will continue to work until deleted)

Edit: I wonder; Does this work well in vJASS?

Re: Line Tower Wars & Linked Lists

Posted: Fri Apr 29, 2016 6:44 pm
by Ian
You wouldn't seriously want to loop through each node though in lists that have frequent removal. Right?

Re: Line Tower Wars & Linked Lists

Posted: Fri Apr 29, 2016 6:45 pm
by 3ICE
Correct. This only works fast because we know the list will never grow beyond size 10. (Or however many players you have.)

That double iteration was also unnecessary.
Pseudocode fixed wrote:

Code: Select all

function del takes pointer target returns nothing
  pointer p = first
  loop
    exitwhen p.next == target
    p = p.next
  end loop
  pointer q=p.next.next
  //delete here using the p → target → q invariant property
end function

Re: Line Tower Wars & Linked Lists

Posted: Fri Apr 29, 2016 7:01 pm
by Ian
Linked lists seem to be pretty unnecessary in Warcraft III. Is there any reason why you would use a linked list over indexing (in general)? What are good uses of linked lists anyway?

Edit: I did some reading, and I guess the order of data and data insertion is a good reason to use a linked list. I just can't think of too many things that require that. Seems like for simply looping through data, indexing is fine.

Re: Line Tower Wars & Linked Lists

Posted: Fri Apr 29, 2016 7:51 pm
by 3ICE
Good insight. The only reason I used lists is because you mentioned them in your first post. I don't like linked lists. In fact I would never ever want to use a linked list for anything.* Not even in C++.

Sure it has nice advantages like cheap extensibility (each addition being a constant time operation) as opposed to arrays which can go out of bounds and then you have to copy everything into a new, bigger array. which takes O(n) time.
But the trade off for this extensibility is significant; hours of my time is wasted on debugging complicated low level code and deciphering pointer arithmetic. (I even made a mistake in the 10 lines of very simple pseudocode above.)

vJASS has to translate these abstract pointers to proper, JASS compatible handles too. (I don't know how that works, if it does at all. Does JASS even have structs?)
And everything is stored in arrays behind the scenes anyway. JASS doesn't have linked lists.

I've messed up so many linked list implementations and encountered so many Null Pointer Exceptions... I hate coding linked list data types in C.
Arrays are just so much easier to work with. And even better are high level languages.

* The one redeeming factor: Java's generic List<> implementation is safe and hard enough to mess up that I am okay with using linked lists there.
But only if I can let java manage the LinkedList and I don't have to touch the low level stuff myself. I just add elements to the end for cheap (as in few CPU cycles) and let java handle the (rare!) delete operations from the middle.