## How to Prevent Enemy Overlap

I am working on a 2D side-scrolling action platformer.

I am currently working on the state logic for my enemies. These are humanoid enemies that walk on the ground

They currently have idle, patrol, chase, engage, and attack states.

The default state is patrol, where they walk back and forth on a platform. If they encounter a wall or cliff, they idle for a few seconds then turn around and patrol in the other direction.

If the player comes within a chase_radius, they start chasing the player. If the player comes within an attack_radius, they enter an engaged state where they attack every few seconds.

Currently, I don’t have enemies colliding with one another. I allow them to overlap each other. This is nice in the event that two enemies are patrolling in opposite directions. They simply walk passed each other.

The problem is that when two enemies are chasing a player, when one enters the engaged state, they stop and idle until they attack. The second enemy continues to walk until they too are within attack range. They then stop directly on top of the previous enemy and idle until they attack.

In this case, the enemies pretty much completely overlap and it turns an interesting situation with two enemies into a situation with essentially one enemy.

What are some techniques or design choices I can make to prevent this ugly overlap? Ideally, I’d like the enemies to be able to walk passed each other when they are not engaged, but to do something different during combat so that they don’t end up overlapping.

Similar Questions:

1. Enemies overlapping (involves pathfinding, and isn’t applicable to 2D sidescroller where enemies walk on ground.)
2. How to avoid enemies overlapping each other when chasing player in Unity?

## algorithm for grouping elements (defined by time range, weight, location) based on time range overlap (groups are constrained by params)?

Let each element be an individual. Consider that an individual is defined such that each individual has a time range, weight, and location.

The goal is to group together individuals whose time ranges overlap while ensuring that, within the group, the sum of the weights of the individuals do not exceed a certain threshold. At the same time, it is desirable to minimize the total distance between the individuals in the group. As many individuals as necessary can be placed into a group as long as the weight constraint is met.

The goal is to have as many individuals grouped (that is at minimum paired) as possible while minimizing the total distance between individuals in groups.

For example, consider an example in the discrete time case where there are ten time intervals. [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]. The weight threshold is 4 and the location of the individuals are points on the 1-D line of integers. Say that we have the following individuals:

A: time range: [1, 2, 3] | weight: 1 | location: 1 B: time range: [2, 3, 4] | weight: 2 | location: 2 C: time range: [4, 5, 6] | weight: 2 | location: -3 D: time range: [4, 5, 6] | weight: 3 | location: -3 

Note:

• A and C cannot be grouped because they do not have overlapping time ranges.
• grouping together A and B gives is preferable to grouping together B and C because A and B are closer together.
• C and D cannot be grouped because the sum of their weights exceed 4. Does any one have a recommended algorithm for solving a problem like this?

I’ve looked at the examples in (Studies in Computational Intelligence 666) Michael Mutingi, Charles Mbohwa (auth.) – Grouping Genetic Algorithms_ Advances and Applications-Springer International Publishing (2017). However, none of the grouping algorithms seem very fitting.

## Do instantaneous effects overlap? [duplicate]

• When a creature is hit with more than one fireball simultaneously, do they take damage from all of them? 4 answers

## Premise

Two wizards hold an action to cast fireball on the first humanoid that walks through a door. A humanoid walks through the door.

## Backround

DMG errata version 2.0 page 1

Combining Game Effects (p. 252). This is a new subsection at the end of the “Combat” section:

Different game features can affect a target at the same time. But when two or more game features have the same name, only the effects of one of them—the most potent one—apply while the durations of the effects overlap. For example, if a target is ignited by a fire elemental’s Fire Form trait, the ongoing fire damage doesn’t increase if the burning target is subjected to that trait again. Game features include spells, class features, feats, racial traits, monster abilities, and magic items. See the related rule in the “Combining Magical Effects” section of chapter 10 in the Player’s Handbook.

## Question

Does the humanoid take damage from both fireballs? or does the humanoid only take damage from the “most potent” fireball?

## Find all polygons from a set that overlap a given polygon (convex case)

Problem: Given a set of N non-overlapping convex polygons {S_i, i=1..N} defined by their vertex coordinates (x,y) and a convex polygon P, also defined by its vertex coordinates, find all polygons S_i that overlap with P. Assume an algorithm to test whether a pair of polygons overlap already exists.

Constraints: We are allowed to perform operations of O(N) on {S_i} without knowledge of P (initialization step). After that, given an arbitrary P the algorithm should perform in approximately O(log N) time when S consists of polygons of uniform size. Hence, an algorithm that just tests P against every S_i will be rejected.

Solution idea: On initialization, insert all vertices of the polygons of {S_i} into a kd-tree K and associate each vertex with its associated polygon. Store the diameter dS of the largest polygon in {S_i}. Then given a polygon P, calculate the diameter dP of P. Find all vertices in K that are no farther than max(dS,dP)/2 (?) from any vertex in P. Test P against only faces that contain the vertices in K.

Since lookup in K is a log(N) operation, then if N is large and dP is approximately equal to dS then the number of tests should be << N.

Any other solution ideas? Google is yielding nothing of value.

Similar to How to find polygons overlap reign but with additional constraints.

## Snap packages overlap and uneeded?

I’m not keen yet on the benefits of snap, and I may have some trouble here with my gnome-3-* snaps. I don’t see how this can be right. Please help.

~ $snap list Name Version Rev Tracking Publisher Notes audio-recorder 1.1.2+rev1413+pkg-7036 30 beta brlin - chromium-ffmpeg 0.1 9 stable canonical✓ - core 16-2.37.2 6405 stable canonical✓ core core18 18 731 stable canonical✓ base gnome-3-26-1604 3.26.0 78 stable canonical✓ - gnome-3-28-1804 3.28.0-8-gc14de1f.c14de1f 15 stable canonical✓ - gnome-3-30-1804 3.30.0 1 edge ken-vandine - gnome-calculator 3.30.1 260 stable/… canonical✓ - gnome-characters 3.30.0 139 stable/… canonical✓ - gnome-logs 3.30.0 45 stable/… canonical✓ - gnome-system-monitor 3.30.0 57 stable/… canonical✓ - gtk-common-themes 0.1-7-g1feddba 1122 stable/… canonical✓ - indicator-sensors 0.9-5-ge09201c 95 stable alexmurray - mailspring 1.5.7 326 stable foundry376✓ - opera 58.0.3135.79 26 stable opera-software✓ - shotcut 19.02.28 43 stable meltytech✓ classic signal-desktop 1.22.0 104 stable snapcrafters - spotify 1.1.0.237.g378f6f25-11 34 stable spotify✓ - stress-ng 0.09.54-20190221-5284-8c36aa4d 503 stable cking-kernel-tools - ~$   lsblk NAME   MAJ:MIN RM   SIZE RO TYPE MOUNTPOINT loop0    7:0    0  14.5M  1 loop /snap/gnome-logs/45 loop1    7:1    0 154.5M  1 loop /snap/signal-desktop/104 loop2    7:2    0  34.8M  1 loop /snap/gtk-common-themes/1122 loop3    7:3    0 154.7M  1 loop /snap/opera/24 loop4    7:4    0  42.1M  1 loop /snap/gtk-common-themes/701 loop5    7:5    0    13M  1 loop /snap/gnome-characters/124 loop6    7:6    0   3.9M  1 loop /snap/stress-ng/503 loop7    7:7    0 135.8M  1 loop /snap/gnome-3-28-1804/9 loop8    7:8    0  53.7M  1 loop /snap/core18/677 loop9    7:9    0    13M  1 loop /snap/gnome-characters/139 loop10   7:10   0   2.3M  1 loop /snap/gnome-calculator/260 loop11   7:11   0 140.7M  1 loop /snap/gnome-3-26-1604/78 loop12   7:12   0 174.5M  1 loop /snap/spotify/32 loop13   7:13   0   174M  1 loop /snap/spotify/34 loop14   7:14   0    91M  1 loop /snap/core/6405 loop15   7:15   0 105.4M  1 loop /snap/shotcut/43 loop16   7:16   0 154.7M  1 loop /snap/opera/25 loop17   7:17   0  53.7M  1 loop /snap/core18/731 loop18   7:18   0  53.7M  1 loop /snap/core18/719 loop19   7:19   0 174.4M  1 loop /snap/spotify/31 loop20   7:20   0 143.2M  1 loop /snap/gnome-3-28-1804/11 loop21   7:21   0 143.4M  1 loop /snap/gnome-3-28-1804/15 loop22   7:22   0 140.7M  1 loop /snap/gnome-3-26-1604/74 loop23   7:23   0  91.1M  1 loop /snap/core/6259 loop24   7:24   0 194.4M  1 loop /snap/mailspring/326 loop25   7:25   0  34.6M  1 loop /snap/gtk-common-themes/818 loop26   7:26   0 194.4M  1 loop /snap/mailspring/309 loop27   7:27   0   3.7M  1 loop /snap/gnome-system-monitor/57 loop28   7:28   0 108.7M  1 loop /snap/audio-recorder/30 loop29   7:29   0 154.5M  1 loop /snap/signal-desktop/103 loop30   7:30   0 148.8M  1 loop /snap/signal-desktop/101 loop31   7:31   0 154.7M  1 loop /snap/opera/26 loop32   7:32   0 194.4M  1 loop /snap/mailspring/319 loop33   7:33   0  17.6M  1 loop /snap/chromium-ffmpeg/9 loop34   7:34   0   112M  1 loop /snap/shotcut/41 loop35   7:35   0   2.3M  1 loop /snap/gnome-calculator/238 loop36   7:36   0    91M  1 loop /snap/core/6350 loop37   7:37   0   596K  1 loop /snap/indicator-sensors/95 loop38   7:38   0 128.5M  1 loop /snap/gnome-3-30-1804/1 loop39   7:39   0   3.9M  1 loop /snap/stress-ng/491 loop40   7:40   0   3.9M  1 loop /snap/stress-ng/497 loop41   7:41   0   112M  1 loop /snap/shotcut/40 loop42   7:42   0   556K  1 loop /snap/indicator-sensors/71 

## How can I check to see if two cylinders overlap?

Is there a simple way for me to determine if a cylinder a and cylinder b overlap in the 3D space? I have spent a few hours looking into this, but haven’t yet found a solution.

For a little while, I thought that MemberRegion[] might be useful, but it does not seem to be working in 3 dimensions.

For example, here, above, two cylinders are overlapping

## Minimum vertex cover with minimum overlap of one side

In a bipartite graph $$(X+Y,E)$$, it is possible to find a minimum vertex cover in polynomial time, by Konig’s theorem.

Suppose the minimum size is $$s$$. Is there an efficient algorithm for finding a vertex cover $$S$$ of size $$s$$, such that $$S\cap X$$ has a minimum cardinality?

What I could do so far is to formulate this problem as an ILP where each vertex $$u\in X$$ has a variable $$x_u$$ and each vertex $$v\in Y$$ has a variable $$y_v$$. Its LP relaxation is:

\begin{align} \text{minimize} && \sum_{u\in X} x_u && \ \text{subject to} && x_u + y_v \geq 1 && \forall (u,v)\in E \ && \sum_{u\in X} x_u + \sum_{v\in Y}y_v = s \ && 1\geq x_{u}\geq 0, 1\geq y_v \geq 0 && \forall u\in X, v\in Y \end{align}

But I do not know how to check whether this ILP has an integer solution.

Is there a better approach to this problem?

## Merging two splay trees whose ranges may overlap in $O(\log N)$

I have two splay trees, $$A$$ and $$B$$.

When every element in $$A$$ is smaller than every element in $$B$$, we can merge them in $$O(\log N)$$.

My question is; when all elements of $$A$$ are not necessarily smaller than all elements of $$B$$, how can we still merge $$A$$ and $$B$$ in $$O(\log N)$$?

Splay $$A$$‘s largest element, splay $$B$$‘s smallest element. The root $$R_A$$ of $$A$$ doesn’t have a right child anymore, and the root $$R_B$$ of $$B$$ doesn’t have a left child anymore. Compare $$R_A$$ and $$R_B$$. If $$R_B$$ is bigger than $$R_A$$, make $$R_B$$ the right child of $$R_A$$, which fails when $$R_A$$ is larger than $$R_B$$.