Resources That Have Yet To Be Coded

[Flux]

Big Integer multiplication.

Use FFT for faster time complexity? But if that's the only use, it feels like it isn't "efficient" to do so.

 

[Magtheridon96]

There's no harm in having it.

Are you arguing for the sake of arguing?

Edit

from cmath import exp, pi
 
def fft(x):
    N = len(x)
    if N <= 1: return x
    even = fft(x[0::2])
    odd =  fft(x[1::2])
    T= [exp(-2j*pi*k/N)*odd[k] for k in range(N//2)]
    return [even[k] + T[k] for k in range(N//2)] + \
           [even[k] - T[k] for k in range(N//2)]
 
print( ' '.join("%5.3f" % abs(f) 
                for f in fft([1.0, 1.0, 1.0, 1.0, 0.0, 0.0, 0.0, 0.0])) )

FFT is really short and easy to write.
In JASS, this would be up to 3-4 times as large at best.

Edit

OK, Admittedly, a BigInteger Multiplication function would have to use a slightly different implementation.
And by Slightly, I mean that it has to work in some finite field instead of the reals for the sake of precision.

You're right, it's not so useful.

We had a BigInteger library written a few years ago. I don't know if it's still up, and I don't know what multiplication algorithm it used.
Whatever it was, I'm pretty sure it was nothing close to Schonhage-Strassen.

 

[Almia]

Max Flow, FFT, Convex Hull, Simplex, etc...?

I wrote FFT once in vJASS, but I got bored and threw the code away.
It can be done recursively pretty safely, but iterative is probably a lot better (idk).

Convex Hull is pretty short to write. It wouldn't require a resource on its own. What's not so trivial is Convex Hull in 3D.

It's not immediately obvious what Simplex would be useful for, but it would be cool to have it out there and see what people could make out of it.

and don't forget about Regex

 

[Magtheridon96]

You can implement Regex to match expressions of length M to regular expressions of length N in O(N*M) by Dynamic Programming without any preprocessing.

With preprocessing, you can construct a Deterministic Finite Automaton in worst case O(2^M) time and space, but this would allow you to answer regex match queries in O(N) time.

 

[Mr.Pockets00000]

The periodic timer wouldn't be accurate. You'd need something that instantly catches items as they appear on the map. This may require a lot of h4x0ring :|
Are there any abilities that fire or change somehow when an item is placed?

You'd need to find something as smart as the Undefend trick, but for items.

A possible work around might be to wrap the item create function in a library, so that you now use the library's item creation function when generating items (easier detecting). Then make a trigger that fires on pawn and purchase item as well as destroy and use item that checks charges less equal to 1. Why wouldn't this solve the problem?

Just call whatever function you use to register items to the system in all possible item creation and destruction scenarios.

 

[Wietlol]

It wouldnt solve the problem because you cant implement it in your map.
All items that are created by already implemented stuff will not be able to work.

However, it is not a bad thing to do for own usage.

 

[leandrotp]

I found an exploit we can use to make an Item Enter Region event for specific items.
We can't do this for all items in general with my method though :|

I'll be testing my hypothesis as soon as I get Warcraft III and NewGen up and running on my new machine~

How is this possible? I've never found such thing, could you please post it here?

 

[BPower]

How is this possible? I've never found such thing, could you please post it here?

We'll never know.

I see two mediocre good options if you need to index items:

1.) Go with the a PUI like design. PurgeandFire also mentioned that on page 2/3.
Meaning you index an item the first time GetItemIndex(item) is called.
You clean either periodically or after x indexed item handles.
This gives you an onDeindex event, but no reliable onIndex event.

2.) You can detect the item on the first unit interaction by using the most common
unit item events. That makes also sense, as items don't have a big meaning
without beeing inside an inventory.
Again you clean periodically or after x items indexed.
This also gives you an onDeindex event, but no reliable onIndex event.

 

[leandrotp]

We'll never know.

Why not? Is Magtheridon96 retired from the forums?
And I'm not asking for item indexing system, I just wanna know how he managed to detect when a specific item enters a region.

 

[BPower]

Curve ( Projectile ) system using the cubic Bézier curve, a wrapper for quadratic curves as they are more likely useful in map making
and the option to add n cubic curves with proper calculated continuity. It should not be restricted to missiles
as you could also draw special effects / images on the curve, but you could build a missile system based on it.

That would be awesome.

 

[Almia]

Curve ( Projectile ) system using the cubic Bézier curve, a wrapper for quadratic curves as they are more likely useful in map making
and the option to add n cubic curves with proper calculated continuity. It should not be restricted to missiles
as you could also draw special effects / images on the curve, but you could build a missile system based on it.

That would be awesome.

wait, don't we have already a that kind of library?

[edit]

Some Interpolation stuff

 

[BPower]

mmmh nice, but we could extend it by adding code for proper continuity to
create bezier curves of n order. The script only allows linar, quadratic and cubic.
For higher order you would merge multiple cubic curves to one.

Could also be fancy syntax

struct Point
real x
real y
real z
endstruct

struct BezierCurve
Point p1
Point p2
Point p3
Point p4
// Code
endstruct

 

[Ardenian]

Has someone ever tried to code/ coded a system to simulate the obstacle-checking tiles ( green and red) when
trying to choose a placement for a building ?

 

[Zwiebelchen]

Has someone ever tried to code/ coded a system to simulate the obstacle-checking tiles ( green and red) when
trying to choose a placement for a building ?

Hmm, can you give an example of a possible use-case for this?

 

[Ardenian]

Hmm, can you give an example of a possible use-case for this?

For example this one: http://www.hiveworkshop.com/forums/world-editor-help-zone-98/pylon-building-system-277847/

Users could define what should block the building or what should allow it.

 

[Wietlol]

I can make it but only for single player support.
If we can find a way to make it for multiplayer, it would be good enough.

The trick is placing a lot of building blockers.

 

[Ardenian]

Oh, that is indeed a problem. I think there is no solution up to now, is there ?
Same problem as with the custom interfaces, like tech trees and inventories only being visible for one player.

 

[Wietlol]

Custom interfaces should be visible for one player, then recreated for each human player so all players can be in the custom interface without having to see what player 1 is watching.

Custom interfaces work properly in multiplayer.
Custom building restrictions are not (yet).

 

[Almia]

mmmh nice, but we could extend it by adding code for proper continuity to
create bezier curves of n order. The script only allows linar, quadratic and cubic.
For higher order you would merge multiple cubic curves to one.

Could also be fancy syntax

struct Point
real x
real y
real z
endstruct

struct BezierCurve
Point p1
Point p2
Point p3
Point p4
// Code
endstruct

Is this good enough (cons : the "get" method. will use the de Casteljau algorithm soon):
Bezier struct

 

[Ardenian]

I would like to make some suggestions for additions to this list:

Dungeon Generator	Create an intelligent algorithm to create a compilation of shapes being connected to each other. Find a good balance between randomization, configurability and intelligence.
Carrier	As in StarCraft, create a system that allows the creation of carriers spawning dummy units on attack, functioning as damage media instead of the main unit, moving after a certain algorithm
Sight Range	Create a system that triggers the sight range of all units intelligently, allowing to interact with the sight range, like reducing or increasing it after needs.
Temporary Fog	Create a system that allows to hide visible terrain with a timed delay. For example, visible tiles are covered by Fog of War after 5 seconds without a unit in range and after additional 5 seconds, covered with Black Mask
Pylon	As in StarCraft, create a system to simulate pylons giving power to nearby buildings. No nearby pylon means a building cannot be placed/built and supplied buildings are deactivated if there is no pylon within a certain range, pausing all processes like build process, upgrade process and train process, for example

 

[Almia]

sight range is possible tho it would require spamming dummy units with fixed sight range or revealing the area around it.

also, your suggestions are somewhat not that "useful"

those are like system ideas.

[edit]

For the love of God, nestharus, you ignored this guy:
http://www.hiveworkshop.com/forums/2487066-post58.html

 

[Ardenian]

Well, these are systems I see frequently on the forums, requested or in howcanIdothis-style.
Just collected it a bit, maybe someone is interested.
Working myself on the dungeon generator, for example.

Even though they are systems, they are still resources, aren't they.

 

[Almia]

Well, these are systems I see frequently on the forums, requested or in howcanIdothis-style.
Just collected it a bit, maybe someone is interested.
Working myself on the dungeon generator, for example.

Even though they are systems, they are still resources, aren't they.

a dungeon generator like minecraft's would be great e.g. generate rooms first, randomly linked some rooms either by their nearest room neighbor or just some random rooms. (By linked means building a path)

I'm not sure how are you going to generate the dungeon tho, is it by means of tiles? :V

 

[Ardenian]

Yes, by the means of tiles ( customizable though, one does not necessarily need to use 128 range or tiles).
Basically the rooms are going to be rectangles, not sure for the floors/connections yet,
but they are most likely rectangles, too.

I can already tell my generator is not going to be very intelligent, from coding perspective,
but rather aiming for being useable.

I already spent 100+ hours on it ( believe it or not),
once the current Zephyr is over/ I finished my Zephyr entry
I clean-write it and add documentation to it, releasing it.
It is going to be plain Jass, so vJass 'is not occupied' yet.
A lot of points are a lot easier in vJass, I believe.

 

[Almia]

Good job
Keep it up

As for the GetClosestTile and A*

I am currently writing a QuadTree implementation for my game (currently, I use Brute Force approach to iterate neighbors, I then used Spatial Hash Grids but it worsen the performance(it might be I did something wrong))
so I might as well try writing a vJASS lib of it.

I can also use QuadTree for my Flock System. It also uses Brute Force so I think that's going to improve the performance a lot.

 

[Wietlol]

Sight range can be manipulated the same as health and mana are done nowadays.
There is an item ability that increases sight range.

 

[Ardenian]

Thanks Almia


Yes, but only the sight range as whole. What if you would like to cut off the sight range at one side ?
Surely it is kinda redundant, there are other workarounds, too.

I forgot custom placing requirements, what we talked about before here, these buildings
tiles checking if one can place the building somewhere.

 

[Chaosy]

Pylon system seems interesting.
Though it also seems impossible to do on the same level as in SC2. Mainly because you can't detect when a player is placing a building.

 

[Almia]

Sight range can be manipulated the same as health and mana are done nowadays.
There is an item ability that increases sight range.

Sight Range abilities doesn't stack with itself, so you can't do a hinary conversion to it.

 

[Chaosy]

I think bonusmod allowed increasing sight range by the way?

 

[Almia]

but not in a binary distribution

I have already tested this and it doesn't work just like how other bonuses works

 

[Wietlol]

You can do it the same way how health and mana are done.
Adding 1000, 100, 10 or 1 depending on how much you need.
So if you want to increase by 1350, you do +1000 +100 +100 +100 +10 +10 +10 +10 +10.
You can make binaries out of those instead of powers of 10 to increase efficiency but it is the easiest way of doing it.

 

[Xonok]

Except that you can't. Sight Range doesn't stack.

 

[Almia]

I told you it doesn't work. How do you think binary distribution works?

2 100 sight range won't stack

 

[Wietlol]

But when you remove it, it removes the bonus from lvl 1.
When you add the ability with lvl 1 set to 0 sight range and lvl 2 set to -100 then you can add the ability, set it to lvl 2 then remove it and you have added 100 sight range.

I told you it works, why cant you just believe me?

 

[Almia]

http://www.hiveworkshop.com/forums/lab-715/sight-range-260758/

Huh? Yours doesn't do the same thing at all? I don't see what you're getting at. Perhaps you don't understand what Get Closest Tile Type is supposed to do?

Using either a quad tree or an octal tree, find the closest point with a given type to a point.

It should be called Get Closest Tile By Type

With that, you could have a bonus that only works while you are within 1024 of water.

Spiral search can do it, right? even though not as fast as octrees/quadtrees can.

also i think k-d tree can do it

 

[Almia]

Okay, I think this should work for GetClosestTile :

1) Use a Spiral Search approach to identify tiles. (I think it is OP-safe, and also works better on fixed radius)
2) Use K-D tree. Get all of the points and then build a tree with it. (Not sure of OP-Safe)
3) Use K-D tree. Iterate the points and insert them one by one. With each insert, balance the tree. (Not sure if op-safe as well)
4) Use a Quadtree where each leaf node holds 4 tiles. Starting from the center of the map, subdivide the map. (Not sure if op-safe either)
5) Use an Octree, just like Quadtree. Because it is 4 times larger than a quadtree, I think it is not safe as well.
6) Binary Space Partition ( I need some info for this)

Requirements:
ZLibrary(each tile holds it's rawcode and it's depth?)
TileDefinition or Tile module

Needed information:
How many tiles each variation of map has.(e.g. 32x32, 32x64, 32x96, etc.)

 

[Wietlol]

I think a spiral search is pretty simple to do.
But how would a fixed radius be better on it?

 

[Almia]

I think a spiral search is pretty simple to do.
But how would a fixed radius be better on it?

I mean it works better with it.

Get the axis-aligned bounding box of the radius, get the list of points, do a spiral search with the center of AABB until you go outside the AABB

currently, Spiral Search is the best way to do with it. It is easy to write and implement. Not as fast as other methods do tho, but it is the simplest.

 

[IcemanBo]

Maybe a rectangle search is better.
1) Go to the current tile edge
2) Go in rect-shape, following the tile-edge, around your current tile, and compare the condition for each of the tiles next to your current position of the edge. (you must know how tile definition works for that)
3) If the condition mets, you save the tile distance and tile id as variables. (backup variables)
4) If the condition mets again, you compare distance to your backup value, to know if it's a closer tile, or not.
5) If you finished the rectangular surrounding, nothing was found, you go 128 units further, and repeat.

If you want Get N-ClostestTiles, then something like a list is better. But for only one tile it's probably not needed.
I'm also not very sure how you come to usage of something like OctalTree of this. Mind to elaborate your thoughts?

Also elaborating on this might be cool:

6) Binary Space Partition ( I need some info for this)

 

[Almia]

if we are talking about data structures + kNN search, I think K-D tree is the best.

K-D tree is a tree of points, where each depth of the tree represents Axes.


Binary Space Partition is a basis of K-D tree. you just keep on splitting the planes into 2. I think k-d tree is axis-aligned, BSP isn't

 

[IcemanBo]

Well, I would want to know why you think this is the best, and why you want to use it.

 

[Almia]

K-D tree is mainly used for kNN problems IMO, just as what is stated on it's wiki page : https://en.wikipedia.org/wiki/K-d_tree
It is also always suggested by my friend.

 

[IcemanBo]

Could you explain me without just linking to wikipedia?
I'm interested how you would use it exactly and why.
Look at my example - for for getting one clostest tile, no data structure at all was needed.
For getting a list of N clostets tiles, yes. But it has not to be a special type of tree imo. So I'm curious.

 

[Almia]

I haven't written any K-D trees (yet the tree ds itself) on any languages so Idk how it will work out

 

[Almia]

Okay back to the get closest tile

I have found out that Spiral Search and IcemanBo's solution is still the best so far.

because the current problems for QuadTree, Octree, K-D tree and BSP is the memory management.

When dealing with QuadTrees, a 256*256 map will be required to generate 21845 quadtrees to hold all the tile data in the map. Octrees will take 21845^2 octrees. If we aren't going to use a Table for this, the QuadTree and Octree will fail.

When dealing with K-D trees, it will be required to create a K-D tree per tile type(by tile type I mean their texture) and also for water depth and cliff.
IT is good when dealing with get nearest water tile or cliff, but it is not good for holding tile data because it will be required to create a K-D tree per tile type and updating the K-D tree if a tile is modified will be harsh (because it needs to be balanced)

BSP is just like K-D tree's case.

[Back to the Starter]
Coordinate Transformation
- won't this be easy using a Matrix 2/3? or how about holding the spherical transformation.

A*
- What. Maybe someone should update Ammorth's code.

 

[Cokemonkey11]

Using either a quad tree or an octal tree, find the closest point with a given type to a point.

It doesn't make sense to use an octtree (a data structure for 3D data) for terrain tiles (which are limited to the terrain heightmap, a 2D interface).

 

[Almia]

Yes it doesn't make sense, but what I am saying is that Octree can fulfill the job as well, even tho it is worse in Space complexity

 

[yki01]

is there a freecodecamp.org or coursera.org for wc3 map modding languages? (anti-fascist peeps, please forgive me).

 

[Pinzu]

is there a freecodecamp.org or coursera.org for wc3 map modding languages? (anti-fascist peeps, please forgive me).

Coding macht frei. You will enjoy your future freedom.

Look at tutorials, jass section, other peoples code such as spells or simply convert GUI code to JASS. Finally produce stuff that people can review or post your code and ask for feedback.