Line Tower Wars & Linked Lists

Do you need World Editor help? Ask here!
Forum rules
Before making a new topic:
First, check if your question has already been answered in the Tutorials section.
If you didn't find a solution, use the search function.
If searching didn't help either, you can make a new topic.

Topic title & content:
You must use a descriptive title. (Help plz is not good) (Need help with Dialog buttons is good)
Go into much detail when posting. You should post attachments. Like screenshots of the problem, the map you are making, replays of the error. Or you could even make a screencast (video) of your problem and upload it here.

Spelling:
Grammar seems to be a serious problem amongst teenagers, so use a spell checker or you will get no love.
Read your posts twice, before pressing the reply button.
And do not use profanity. Chatspeak (y r u nub) and Leetspeak (1 C4N S33 H4X) are not welcome here either.

Only World Editor related questions are allowed here!
(Click for Battle.net help) (Click for World Editor help)
Ian
Posts: 76
Joined: Fri Aug 20, 2010 7:56 pm
Realm: US East
Account: Sesamia
Clan: 3ICE
Location: Minnesota

Line Tower Wars & Linked Lists

Unread post 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.
ʎɐqə ɯoɹɟ pɹɐoqʎəʞ ɐ ʎnq ı əɯıʇ ʇsɐl əɥʇ sı sıɥʇ


-Currently semi-inactive

User avatar
3ICE
Admin
Posts: 2629
Joined: Sat Mar 01, 2008 11:34 pm
Realm: Europe
Account: 3ICE
Clan: 3ICE
Location: Hungary
Contact:

Re: Line Tower Wars & Linked Lists

Unread post 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
ImageImageImageImageImage
Image
ImageImage

Ian
Posts: 76
Joined: Fri Aug 20, 2010 7:56 pm
Realm: US East
Account: Sesamia
Clan: 3ICE
Location: Minnesota

Re: Line Tower Wars & Linked Lists

Unread post 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?
Last edited by Ian on Fri Apr 29, 2016 7:14 pm, edited 1 time in total.
ʎɐqə ɯoɹɟ pɹɐoqʎəʞ ɐ ʎnq ı əɯıʇ ʇsɐl əɥʇ sı sıɥʇ


-Currently semi-inactive

User avatar
3ICE
Admin
Posts: 2629
Joined: Sat Mar 01, 2008 11:34 pm
Realm: Europe
Account: 3ICE
Clan: 3ICE
Location: Hungary
Contact:

Re: Line Tower Wars & Linked Lists

Unread post 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.
ImageImageImageImageImage
Image
ImageImage

Ian
Posts: 76
Joined: Fri Aug 20, 2010 7:56 pm
Realm: US East
Account: Sesamia
Clan: 3ICE
Location: Minnesota

Re: Line Tower Wars & Linked Lists

Unread post 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?
ʎɐqə ɯoɹɟ pɹɐoqʎəʞ ɐ ʎnq ı əɯıʇ ʇsɐl əɥʇ sı sıɥʇ


-Currently semi-inactive

User avatar
3ICE
Admin
Posts: 2629
Joined: Sat Mar 01, 2008 11:34 pm
Realm: Europe
Account: 3ICE
Clan: 3ICE
Location: Hungary
Contact:

Re: Line Tower Wars & Linked Lists

Unread post 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?
ImageImageImageImageImage
Image
ImageImage

Ian
Posts: 76
Joined: Fri Aug 20, 2010 7:56 pm
Realm: US East
Account: Sesamia
Clan: 3ICE
Location: Minnesota

Re: Line Tower Wars & Linked Lists

Unread post by Ian »

You wouldn't seriously want to loop through each node though in lists that have frequent removal. Right?
ʎɐqə ɯoɹɟ pɹɐoqʎəʞ ɐ ʎnq ı əɯıʇ ʇsɐl əɥʇ sı sıɥʇ


-Currently semi-inactive

User avatar
3ICE
Admin
Posts: 2629
Joined: Sat Mar 01, 2008 11:34 pm
Realm: Europe
Account: 3ICE
Clan: 3ICE
Location: Hungary
Contact:

Re: Line Tower Wars & Linked Lists

Unread post 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
ImageImageImageImageImage
Image
ImageImage

Ian
Posts: 76
Joined: Fri Aug 20, 2010 7:56 pm
Realm: US East
Account: Sesamia
Clan: 3ICE
Location: Minnesota

Re: Line Tower Wars & Linked Lists

Unread post 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.
ʎɐqə ɯoɹɟ pɹɐoqʎəʞ ɐ ʎnq ı əɯıʇ ʇsɐl əɥʇ sı sıɥʇ


-Currently semi-inactive

User avatar
3ICE
Admin
Posts: 2629
Joined: Sat Mar 01, 2008 11:34 pm
Realm: Europe
Account: 3ICE
Clan: 3ICE
Location: Hungary
Contact:

Re: Line Tower Wars & Linked Lists

Unread post 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.
ImageImageImageImageImage
Image
ImageImage

Post Reply

Who is online

Users browsing this forum: No registered users and 47 guests